「プロジェクトオイラー解説問110」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー解説問110」(2014/03/07 (金) 17:21:59) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*Problem 110 「ディオファントス逆数 その2」 †
次の等式で x, y, n は正の整数である.

1/x + 1/y = 1/n

n = 1260 では 113 の異なる解があり, この n が解の個数が 100 を超える最小の値である.

解の数が 4,000,000 を超える最小の n を求めよ.

注: この問題は Problem 108 を非常に難しくしたケースである. 総当り法で解ける範囲を超えているので, 賢い解き方が求められる.



解説
まずは素朴に式変形をしてみる。
1/x+1/y=1/n
(x+y)/(xy)=1/n
nx+ny=xy
(x-n)(y-n)=n^2
なのでｘ-ｎとｙ-ｎはn^2の約数であればよいと分かります。
n^2の約数はその素因数を
n=p1^a1*p2^a2*,,,pm^amとしますと
n^2の約数の個数は
k=(2a1+1)(2a2+1),,,(2am+1)個となります。
x-n<=y-nとしても一般性は失わないので
条件を満たすｘ、ｙの組はk/2+1個であると分かります。
しかし答えは
9350130049860600
とても大きな数で約数を求めていては間に合いません。
逆から考えます。

ｎを素因数の積として組み立てるとき
n=p1^a1*p2^a2*,,,pm^am
n^2の約数の個数はaiだけで決まります。
またp1<p2<,,<pmとしても一般性は失いません。

するとできるだけ小さなｐに大きなaiを割り当てたほうが同じｘｙの組の個数が得られてもｎは小さくなります。
よってa1>=a2>=,,,>=amとなります。
またpの数列が
2,5,7のように隙間ができるより。
2,3,5,7、、、のように隙間のない連続した素数の時のほうが同じ個数のｘｙの組が得られるのでも小さなｎを作り出せます。
この発想に従いｎを小さい順から生成すればＢｉｇＯ（20000）程度で答えが出ます。
ｎを小さいほうから生成するのには優先順位付きキューを使えばよいでしょう。



この発想でわたしは正答してるのでまあそんなに間違ってはないです。
問題は、問のタイトルがディオファントス逆数となってることで。
おそらく正しい解法はディオファントス方程式と絡めて解くのだと思います。
どなたかアドバイスがあれば嬉しいですね。