http://projecteuler.net/index.php?section=problems&id=73
Problem 319、49時間で席が埋まりました。20時間の空白など、凶悪ぶりが際立ちました。
さて、フォーラムによるとProblem 73が関係あるらしいです。そこでこの問題を改めて考察してみましょう。
1/3と1/2の間に分母が12000までの既約分数がいくつあるか、という問題です。例えば、分母が100なら、100/3 + 1 = 34から100/2 - 1 = 49まで分子を動かして、分母と分子が互いに素ならカウントするとすればよいでしょう。分母が101なら50までなので、上の式ではちょっとまずくて、(101 - 1)/2までとすればよいでしょう。
34秒。この問題は答えだすだけなら簡単です。
ふと思ったのですが、これって、和の取り方を逆にしたらどうなるんでしょうね。要するに分子を固定します。例えば100とすると、分母は201から299ですね。最大は5999ですが、例えば5000だと、10001から14999までとなって、12000を超える部分は考えないことになります。
ほとんど同じくらいの時間がかかりました。gcdを呼び出す回数が同じはずなので。
