Pythonで解が1つしかない線形方程式の係数を見つけるプログラム

値nがあるとすると、方程式a * x + b * y =nが少なくとも1つの解を持つように存在するペア（a、b）[a

したがって、入力がn =4の場合、有効なペアは（1、2）と（1、3）であるため、出力は2になります。

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

• 関数divisors_gen（）を定義します。これにはnがかかります
• divs：=サイズn+1のリストのリスト。そして、各内部リストは1を保持しています
• divs [0]：=1つの要素0のみを含むリスト
• 2からnの範囲のiについては、
  • 範囲1から（n / i）+ 1のフロアまでのjの場合、実行
    • リストの最後のインデックス[i*j]
    にiを挿入します
• divを返しますが、すべての内部リストを逆にします
• メインの方法から、次の手順を実行します-
• 結果：=0
• d_cache：=divisors_gen（n + 1）
• 1からn-1の範囲のaについては、
  • i：=1
  • s：=新しいセット
  • a * i
  • b：=n-a * i
  • d_cache [b]の各dについて、実行します
    • d> aの場合、
      • dがsにない場合は、
        • 結果：=結果+1
    • それ以外の場合、
      • ループから抜け出す
    • dをセットに挿入します
  • i：=i + 1

例

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

def divisors_gen(n):
   divs = [[1] for x in range(0, n + 1)]
   divs[0] = [0]
   for i in range(2, n + 1):
      for j in range(1, n // i + 1):
         divs[i * j].append(i)
   return [i[::-1] for i in divs]

def solve(n):
   result = 0
   d_cache = divisors_gen(n+1)

   for a in range(1, n):
      i = 1
      s = set([])
      while a*i < n:
         b = n - a*i
         for d in d_cache[b]:
            if d > a:
               if d not in s:
                  result += 1
            else:
               break
            s.add(d)
         i += 1
   return result

n = 4
print(solve(n))

入力

4

出力

2