题目186：网络连通性

欧拉计划

Connectedness of a network

Here 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) = S_2n-1 and Called(n) = S_2n where S_1,2,3,... come from the "Lagged Fibonacci Generator":

For 1 ≤ k ≤ 55, S_k = [100003 - 200003k + 300007k³] (modulo 1000000)
For 56 ≤ k, S_k = [S_k-24 + S_k-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) = S_2n-1 和 Called(n) = S_2n ，其中 S_1,2,3,... 都是从如下的“Fibonacci 数产生器”中获得的：

如果 1 ≤ k ≤ 55，那么 S_k = [100003 - 200003k + 300007k3] (modulo 1000000)

否则，如果 56 ≤ k, S_k = [S_k-24 + S_k-55] (modulo 1000000)

如果 Caller(n) = Called(n)，用户无疑是拨错号了，这次拨号自然也就失败了，否则拨号就会成功。

从上面记录的开始，我们定义，如果 X 打给 Y，或 Y 打给 X，那么 X 和 Y 就是朋友。相似的，如果 X 是 Y 的朋友，而 Y 又是 Z 的朋友，则 X 就是 Z 的朋友的朋友，以此类推，我们可以得到一条很长的关系链。

假设首相的号码是 524287。那么，在多少次成功的拨号后，不计算失败的拨号，99% 的用户（包括首相在内）会处在首相的朋友关系链中？