以下是一个有着一百万用户的电话系统的部分记录： $$\begin{matrix}\text{编号} & & \text{呼入} & & \text{接听} \\ 1 & \quad & 200007 & \quad & 100053 \\ 2 & \quad & 600183 & \quad & 500439 \\ 3 & \quad & 600863 & \quad & 701497 \\ \ldots & \quad & \ldots & \quad & \ldots \end{matrix}$$ 这份记录是按如下规则生成的：编号为n的记录中，呼叫者是$S_{2n-1}$, 接听者是$S_{2n}$，而$S_1, S_2, \ldots$是由以下被称为“延迟斐波那契随机数生成器”的规则所生成的序列： $$s_k=\begin{cases}(100003 -200003k + 300007k^3) \bmod 10^6 & 1\le k \le 55, \\ (S_{k-24}+S_{k-55}) \bmod 10^6 & k\ge 56.\end{cases}$$ 呼入号码等于接听号码的记录被称为错误记录（拨错号码），否则为正确记录。

若X、Y曾通过话（不论是X呼入Y还是Y呼入X），则称X和Y是朋友。朋友关系具有自反性和传递性，即每个人都是自己的朋友，且若X是Y的朋友，Y是Z的朋友，那么也称X是Z的朋友，以此类推。

若首相的电话号码是524287，那么在多少次成功呼叫的记录（注意排除失败记录）后，首相的朋友会达到总用户数的$99\%$及以上？

注：原题面中对朋友关系的自反性和终止条件描述不清晰，此处按照原题意思给出了更精确的阐述。

本题难度:

解答

比较典型的并查集问题，套用模板即可解决，结果是$2325629$。

注：以下为Python3代码，因带cache装饰器的记忆化搜索是Python3的新特性。

from functools import *

@cache
def s(k):
    return (100003-200003*k+300007*k*k*k)%1000000 if k<=55 else (s(k-24)+s(k-55))%1000000

root=list(range(1000001))
size=[1]*1000001

def find(x):
    if root[x]!=x:
        root[x]=find(root[x])
    return root[x]

def merge(x, y):
    x,y=find(x),find(y)
    if x!=y:
        if size[x] < size[y]:
            x,y=y,x
        root[y]=x
        size[x]+=size[y]

pm=524287
k=err=0
while size[find(pm)] < 990000:
    k+=2
    if s(k)!=s(k-1):
        merge(s(k),s(k-1))
    else:
        err+=1

print(k//2-err)