题目186：网络连通性
Connectedness of a networkHere are the records from a busy telephone system with one million users:
The telephone number of the caller and the called number in record n are Caller(n) = S2n-1 and Called(n) = S2n where S1,2,3,... come from the "Lagged Fibonacci Generator":
For 1 ≤ k ≤ 55, Sk = 3] (modulo 1000000)
For 56 ≤ k, Sk = k-24 + Sk-55] (modulo 1000000)
If Caller(n) = Called(n) then the user is assumed to have misdialled and the call fails; otherwise the call is successful.
From the start of the records, we say that any pair of users X and Y are friends if X calls Y or vice-versa. Similarly, X is a friend of a friend of Z if X is a friend of Y and Y is a friend of Z; and so on for longer chains.
The Prime Minister's phone number is 524287. After how many successful calls, not counting misdials, will 99% of the users (including the PM) be a friend, or a friend of a friend etc., of the Prime Minister?
题目：
下面是一个有着 100 万用户的繁忙电话系统的记录：
在第 n 条记录中，拨号者和接听者的电话号码分别是 Caller(n) = S2n-1 和 Called(n) = S2n ，其中 S1,2,3,... 都是从如下的“Fibonacci 数产生器”中获得的：
如果 1 ≤ k ≤ 55，那么 Sk = (modulo 1000000)
否则，如果 56 ≤ k, Sk = k-24 + Sk-55] (modulo 1000000)
如果 Caller(n) = Called(n)，用户无疑是拨错号了，这次拨号自然也就失败了，否则拨号就会成功。
从上面记录的开始，我们定义，如果 X 打给 Y，或 Y 打给 X，那么 X 和 Y 就是朋友。相似的，如果 X 是 Y 的朋友，而 Y 又是 Z 的朋友，则 X 就是 Z 的朋友的朋友，以此类推，我们可以得到一条很长的关系链。
假设首相的号码是 524287。那么，在多少次成功的拨号后，不计算失败的拨号，99% 的用户（包括首相在内）会处在首相的朋友关系链中？
页:
[1]