問題
平方数でない正整数 $D$ が与えられる。次の方程式（Pell方程式）
$$x^2 - D y^2 = 1$$
を満たす正整数の組 $(x,y)$ のうち、$x$ が最小となるもの（基本解）を求めよ。
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $D$ | $2 \le D \le 10^6$ | 平方数でないことが保証される |
入出力例
入力例1
2出力例1
3 2入力例2
61出力例2
1766319049 226153980例1: $3^2-2\times2^2=1$。例2: $D=61$ は基本解が異常に大きくなることで有名（フェルマーがウォリスに出した問題）。
概念図: $\sqrt D$ の連分数展開から収束分数を生成し $h_i^2-Dk_i^2=1$ を探す
ヒント
ヒント1（方向性）
$y=1,2,3,\dots$ と全探索して $Dy^2+1$ が平方数になるか調べる方法は、$D=61$ のように基本解が巨大になるケースで全く間に合わない。$\sqrt D$ の連分数展開を使う古典的な理論が必要。
ヒント2（アプローチ）
$\sqrt D$ を連分数展開 $[a_0;\overline{a_1,\dots,a_r}]$（循環連分数）すると、その収束分数 $h_i/k_i$ が Pell方程式の解候補になる。$h_i^2-Dk_i^2=\pm1$ が交互に現れ、$+1$ になる最初の収束分数が基本解を与える。
ヒント3（ほぼ答え）
m, d, a = 0, 1, a0
h_prev2, h_prev1 = 1, a0
k_prev2, k_prev1 = 0, 1
while True:
m = d*a - m
d = (D - m*m)//d
a = (a0+m)//d
h = a*h_prev1 + h_prev2
k = a*k_prev1 + k_prev2
if h*h - D*k*k == 1:
return h, k
h_prev2, h_prev1 = h_prev1, h
k_prev2, k_prev1 = k_prev1, k模範解答
import sys, math
def main():
D = int(sys.stdin.readline())
a0 = math.isqrt(D)
m, d, a = 0, 1, a0
h_prev2, h_prev1 = 1, a0
k_prev2, k_prev1 = 0, 1
if h_prev1 * h_prev1 - D * k_prev1 * k_prev1 == 1:
print(h_prev1, k_prev1)
return
while True:
m = d * a - m
d = (D - m * m) // d
a = (a0 + m) // d
h = a * h_prev1 + h_prev2
k = a * k_prev1 + k_prev2
if h * h - D * k * k == 1:
print(h, k)
return
h_prev2, h_prev1 = h_prev1, h
k_prev2, k_prev1 = k_prev1, k
main()計算量: 連分数の周期長は $D$ に対し経験的に十分小さく、各ステップは多倍長整数の定数回演算。$D\le10^6$ なら実用上一瞬で終わる。
Step-by-Step 解説
Step 1: $\sqrt D$ の連分数展開を漸化式で計算
$m_i,d_i,a_i$ の三つ組で $\sqrt D=[a_0;a_1,a_2,\dots]$ を1項ずつ計算する。この展開は必ず周期的になる。
Step 2: 収束分数を同時に更新
$h_i=a_ih_{i-1}+h_{i-2}$、$k_i=a_ik_{i-1}+k_{i-2}$ で $\sqrt D$ の有理数近似を更新する。
Step 3: $h_i^2-Dk_i^2=1$ を毎回チェック
周期の偶奇を意識せず、最初に条件を満たした $(h_i,k_i)$ を採用すれば正しく基本解が求まる。
Step 4: 多倍長整数でそのまま扱う
基本解が10桁を超えることも珍しくないが、Pythonの整数は任意精度なので問題ない。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| $y$ を1から全探索 | 基本解が巨大になるケースを想定していない | 連分数展開のアルゴリズムを使う |
| $h_i^2-Dk_i^2=-1$ を解と誤判定 | 収束分数は $\pm1$ を交互に取ることを見落とす | 必ず==1を明示的にチェック |
| 浮動小数点で $\sqrt D$ を計算し誤差蓄積 | math.sqrtの精度不足 | math.isqrtで整数演算にとどめる |
次のステップ
- 発展問題: $x^2-Dy^2=-1$ の解の存在判定（周期が奇数長のときのみ解が存在）
- 発展問題: 一般化Pell方程式 $x^2-Dy^2=N$ への拡張（LMM法・連分数併用）
自己評価
理解度: / /
自分の回答:
気づき・メモ: