← 完整题目索引

PROJECT EULER · #0186

网络的连通性

Connectedness of a Network

仅题目 · 已解决原题 ↗

以下是拥有 100 万用户的繁忙电话系统的记录:

接收号码主叫方已叫
1200007100053
2600183500439
3600863701497

记录 n 中的主叫方电话号码和被叫方号码为 Caller(n)=S2n1Called(n)=S2n,其中 S1,2,3, 来自"滞后斐波那契生成器":

对于 1k55Sk=[100003200003k+300007k3](mod1000000)
对于 56kSk=[Sk24+Sk55](mod1000000)

如果 Caller(n)=Called(n) 则假定用户误拨并且呼叫失败;否则调用成功。

从记录开始,如果 X 调用 Y,我们就说任何一对用户 XY 都是朋友,反之亦然。类似地,如果XY的朋友并且YZ的朋友,则XZ的朋友的朋友;对于更长的链条,依此类推。

总理的电话号码是 524287。在成功拨打多少次电话后(不包括误拨),99%的用户(包括总理)会成为总理的朋友、朋友的朋友等吗?

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。