*[[Problem 186:http://projecteuler.net/problem=186]] 「あるネットワークの連結性」 [#ya42e894]
今, 100万人のユーザをもつ電話システムの通信記録がある.
|Rec Nr |Caller |Called|
|1 |200007 |100053|
|2 |600183 |500439|
|3 |600863 |701497|
|... |... |...|
n番目の記録の掛けた側と掛けられた側の電話番号は Caller(n) = &tex{S_{2n-1}}; と Called(n) = &tex{S_{2n}};で与えられる. &tex{S_{1}, S_{2}, ...};は“ラグ付きフィボナッチ生成器”で定義される.
1 ≤ k ≤ 55については, &tex{S_{k} = [100003 - 200003k + 300007k^{3}] (modulo 1000000)};
56 ≤ kでは, &tex{S_{k} = [S_{k-24} + S_{k-55}] (modulo 1000000)};である.
もしCaller(n) = Called(n)であれば, ユーザは間違って電話を掛けたとされ通信は切断される. そうでない場合には, 通信は成功している.
XがYに電話を掛けるかその逆のときに, ユーザXとユーザYが友達であると呼ぶ. 同様に, XがYの友達であるかつYがZの友達であるとき, XがZの友達の友達であると呼ぶ. 同様にして長い連鎖が得られる.
首相の電話番号は524287である. 何回電話を掛けると99%のユーザ (首相自身も含む) が首相の友達になるだろうか?
''(注: 切断された通信は数えない.)''