しょぼんブログ

数学の色々とか様々とか

No.2253 Ignore Subtle Differences 別解と補足

問題解説

問題

yukicoder.me

この解説は以下のブログに書いたことを抜き出したものです。

shobon2019.hatenablog.com

一般解・漸化式を楽に求める手段

yukicoder の解説で a^2-4ab+b^2=1 の整数解を求めるとありましたが, その一般解や漸化式を楽に求める手段を紹介します.

1 つ目の方法は Wolfram|Alpha に頼ることです. Wolfram|Alpha にそのまま a2-4ab+b2=1 と打ち込めば, 整数解の一般項が求まります. それを実装すれば答えを満たす組が出現します.

k = 15
x = round(((2+3**.5)**k-(2-3**.5)**k)/(2*3**.5))
y = round((1/6)*(3*(2-3**.5)**k-2*3**.5*(2-3**.5)**k+3*(2+3**.5)**k+2*3**.5*(2+3**.5)**k))
print(0,0)
print(x,y)
print(y,x)

2 つ目の方法は Generic two integer variable equation solver というサイトを使うことです. 方程式はちょうど「 ax^2+bxy+cy^2+dx+ey+f=0 」 の形になっており, このサイトはその解を満たす漸化式を教えてくれます. すごいサイトです.
上のサイトは競プロでは役に立つことは少ないですが, Project Euler というコンピュータを駆使して数学問題を解くサイト（先生！Project Euler は競プロは含まれますか？）では様々な問題で役に立ちます. Generic two integer variable equation solver はお気に入り登録してもいいかも？

別解 (0, 0), (2x, 0), (x, y) を考える

解説の他に別解もあるので紹介します. (0, 0), (2x, 0), (x, y) がほぼ正三角形をなすことを考えます. これは二等辺三角形なので 4x^2 + 1 = x^2 + y^2 か 4x^2 - 1 = x^2 + y^2 が成り立てばよいです.

ここから直接さきほどのやり方で一般項を求めることができますが, 今回は別のアプローチも効きます.

「ほぼ正三角形」が正三角形に非常に近いことを考えると, y の値が \sqrt{3} x 付近になるべきです. よって, x を固定して y = \sqrt{3} x の付近を調べればよいです. x \gt 10^8 を調べると x = 109552575, y = 189750626 が引っかかり, これはギリギリ問題文の制限をクリアしてるので AC です.

for x in range(10**8, 5*10**8+1):
    f = int((x*x*3)**.5)
    for y in range(f-2, f+3):
        if y*y + x*x - 1 == 4*x*x:
            print(0, 0)
            print(0, 2*x)
            print(y, x)
            exit()