Pythonで4つのパラメータを持つ方程式の解となるペア(x, y)の個数を求めるプログラム

問題の概要

4つの整数 a、b、c、d が与えられたとき、次の方程式を満たすペア (x, y) の個数を求めます。

x² + y² = (x × a) + (y × b)

ただし、x の範囲は [1, c]、y の範囲は [1, d] とします。

たとえば、入力が a = 2、b = 3、c = 2、d = 4 の場合、出力は 1 になります。このとき条件を満たすのは (2, 3) のみです。実際、2² + 3² = 13 であり、(2 × 2) + (3 × 3) = 13 となるため、等式が成立していることが確認できます。

解法のアプローチ

この問題は、方程式を y についての二次方程式として変形することで効率的に解けます。式を整理すると、次のようになります。

y² − b·y + (x² − a·x) = 0

この二次方程式が整数解 y を持つかどうかは、判別式 D = b² − 4(x² − a·x) を調べることで判定できます。D が完全平方数であり、y = (b ± √D) / 2 が 1 以上 d 以下の整数になるとき、その y は有効な解となります。

アルゴリズムの手順

• 答えを格納する変数 ans を 0 で初期化します。
• x を 1 から c まで順に処理します。
  • l = x × (x − a) を計算します。
  • 判別式 det2 = b² − 4 × l を計算します。
  • det2 が 0 に等しく、b が偶数で、1 ≤ ⌊b / 2⌋ ≤ d を満たす場合は、ans を 1 増やして次の反復へ進みます（重解のケース）。
  • det2 が 0 より大きい場合は、以下を判定します。
    • det を det2 の平方根の整数部分とします。
    • det² が det2 に等しく、かつ (b + det) が偶数である場合：
      • 1 ≤ ⌊(b + det) / 2⌋ ≤ d ならば、ans を 1 増やします。
      • 1 ≤ ⌊(b − det) / 2⌋ ≤ d ならば、ans を 1 増やします。
• 最後に ans を返します。

Pythonでの実装例

それでは、上記の手順を実際の Python コードで確認してみましょう。

def solve(a, b, c, d):
   ans = 0
   for x in range(1, c + 1):
      l = x * (x - a)

      det2 = b * b - 4 * l
      if det2 == 0 and b % 2 == 0 and 1 <= b // 2 <= d:
         ans += 1
         continue
      if det2 > 0:
         det = int(round(det2 ** 0.5))
         if det * det == det2 and (b + det) % 2 == 0:
            if 1 <= (b + det) // 2 <= d:
               ans += 1
            if 1 <= (b - det) // 2 <= d:
               ans += 1
   return ans

a = 2
b = 3
c = 2
d = 4
print(solve(a, b, c, d))

入力

2, 3, 2, 4

出力

1

計算量のポイント

このアルゴリズムは x の各値に対して定数時間の計算しか行わないため、全体の時間計算量は O(c) です。y の候補をすべて試す O(c × d) の素朴な全探索と比べ、d が大きいケースでも高速に動作するのが大きな利点です。二次方程式の判別式を活用することで、数学的な性質をそのままアルゴリズムに落とし込んだ美しい解法といえます。