巨大阶乘
|
给定素数p，定义
$$N(p,q)=\sum_{n=0}^qt_np^n,$$
其中$t_n$由以下随机数生成器生成：
\begin{align*}
s_0&=290797, \\
s_{n+1}&=s_n^2 \bmod 50515093, \\
t_n = s_n \bmod p
\end{align*}
记$NF(p,q)$为$N(p,q)$的阶乘的质因数分解中p的次数。
已知$NF(3,10000) \bmod 320=624955285$，求$NF(61,10^7) \bmod 61^{10}$。
|
本题难度:
|
解答
|
显然
$$NF(p,q)=\lfloor\frac{N(p,q)}{p}\rfloor+\lfloor\frac{N(p,q)}{p^2}\rfloor+\ldots,$$
而根据定义，$N(p,q)$是关于p的多项式，且每一项的系数都不超过p，因此
$$NF(p,q)=\sum_{i=1}^q\sum_{j=i}^qt_jp^{j-i}=\sum_{i=1}^qt_i\sum_{j=0}^{i-1}p^j=\frac{1}{p-1}\sum_{i=1}^qt_i(p^i-1),$$
直接计算即得结果$605857431263981935$。
p=61
m=61**10
s=290797
x=1
r=0
for i in range(1,10**7+1):
s=(s*s)%50515093
t=s%p
r=(r+t*x)%m
x=(x*p+1)%m
print r
|
| |
