PythonでさまざまなサブシーケンスGCDの数を見つけるプログラム

正の値の配列numがあるとします。 numsのすべての空でないサブシーケンスの中から異なるGCDの数を見つける必要があります。私たちが知っているように、数列のGCDは、数列内のすべての数を均等に分割する最大値です。

したがって、入力がnums =[4,6,18]の場合、gcd（[4]）=4、gcd（[6]）=6、gcd（[18]）=18であるため、出力は4になります。 gcd（[4,6]）=2、gcd（[4,18]）=2、gcd（[6,18]）=6、gcd（[4,6,18]）=2なので、すべての数値は[ 4,6,18,2]、4つの数字があります。

これを解決するには、次の手順に従います-

• T：=最大数+ 1

• nums：=すべての異なる数のnumsを含む新しいセット

• ans：=0

• 1からT-1の範囲のxの場合、実行

  • g：=0

  • xからT-1の範囲のyについては、各ステップでxずつ更新します。

    • yがnumsの場合、

      • g：=gcd（g、y）

    • gがxと同じ場合、

      • ループから出てくる

  • gがxと同じ場合、

    • ans：=ans + 1

• ansを返す

例

理解を深めるために、次の実装を見てみましょう

from math import gcd
def solve(nums):
   T = max(nums) + 1
   nums = set(nums)
   ans = 0

   for x in range(1, T):
      g = 0
      for y in range(x, T, x):
         if y in nums:
            g = gcd(g, y)
         if g == x:
            break

      if g == x:
         ans += 1

   return ans

nums = [4,6,18]
print(solve(nums))

入力

[4,6,18]

出力

4