Problem 198 (途中経過)

Problem 198 - Project Euler
まだ，解けていませんが，考えをまとめるために，メモ．
(つまり，間違ったことを書いている可能性アリ)

How many ambiguous numbers x = p/q, 0 x 1/100, are there whose denominator q does not exceed 10^8?

まず目につくのは，探索範囲の広さ．
0 < x < 1/100 で， 分母が 10^8 を越えない有理数xはざっと見積って10^12から10^16くらい(かなりテキトウ)．
なので，全探索は問題外．
一方，解のおおまかな個数を考える．
x = 1/2n は近似有理数として，0/1 と 1/n を持つ．
従って，解の個数はおおまかに見積って 10^8 くらい．
つまり，解を列挙するタイプのアルゴリズムは，無駄なく列挙したとしても，少くとも 10^8 くらいの計算が必要．
これはあまり，良いアルゴリズムではない．
そこで，曖昧数 x は二つの有理数 p/q, r/s の中点であること利用する．
(p/q, r/s の分母の小さいほうを探索するとすれば，探索範囲を 10^6 くらいにできるのでは，と楽観的に考える．)
x で考えるのではなく， p/q, r/s のほうで考えることにする．
p/q < r/s として，p/q を固定して，r/s を探すことにする(r/s は複数存在する)．
まず，条件として，p/q, r/s はあるFarey数列でとなりあっているので，
qr - ps = 1.
これより，r = (ps + 1)/q. r は整数であるから， s = -p^(-1) (mod q) を満たす．
p^(-1) (mod q) は拡張ユークリッドの互除法で求められる．
よって，r/s は求められる．(必要十分か？)
つぎに，x を考える． x = (p/q + r/s)/2 だから，
x = (ps + qr)/(2qs) = (2ps + 1) / (2qs).
気になるのは x が既約かどうか，つまり， gcd ( 2ps+1, 2qs) = 1 かということ．
まず，2ps+1 が 2 とも， s とも，互いに素であることは明らか．
よって，考えるべきは，2ps+1 と q が互いに素か．
2ps +1 = -2pp ^(-1) + 1 (mod q) = -1 (mod q) = kq -1 = (k-1)q + (q-1).
q-1 と q は互いに素だから，2ps+1 と q は互いに素．
なので，2qs が 10^8 を越えない範囲で考えてやればいいと思っている．

追記

実装したけど，どうやら間違っているらしい．う~ん．