题目描述
For any prime $p$ the number $N(p,q)$ is defined by $N(p,q) = \sum_{n=0}^q T_n*p^n$
with $T_n$ generated by the following random number generator:
\begin{eqnarray}
&&S_0 = 290797\\
&&S_{n+1} = S_n^2 mod 50515093\\
&&T_n = S_n mod p\\
\end{eqnarray}
Let $Nfac(p,q)$ be the factorial of $N(p,q)$.
Let $NF(p,q)$ be the number of factors $p$ in $Nfac(p,q)$.
You are given that $NF(3,10000) mod 3^{20}=624955285$.
Find $NF(61,10^7)$ mod $61^{10}$
题意
题意说的有点麻烦，我简化一下
$T_i$是随机生成的数据，$N(p,q)=\sum_{n=0}^q T_n*p^n$
问你$N(p,q)$的阶乘里面，质因数分解以后$p$的指数膜$p^{10}$答案是多少．
分析
首先可以观察到的是，$T_i$很小，而且他是随机的，我们显然要把他存起来．
然后一个比较显然的结论是
$$
n!质因数分解后素因子p的数量为\lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + \cdots
$$
$$
\because 最后的答案要膜 p^{10} \therefore 我们统计的时候，对于第一项，我们统计指数为 [1,10]的，第二项[2,11],然后枚举项统计答案即可
$$
代码
给大佬递上我奇丑无比的代码 (/ω＼)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using namespace std;
const int maxm = 1e7+1;
const int pow_num = 10;
long long T[maxm+100];
const int p = 61;
long long powp[1000];
void init(){
powp[0] = 1;
for(int i = 1;i<=pow_num;i++) powp[i] = powp[i-1]*p;
long long s0 = 290797;
for(int i = 1;i<maxm;i++) T[i] = (s0=s0*s0%50515093)%p;
}
int main(){
init();
long long ans = 0;
const long long mod = powp[pow_num];
for(int i = 1;i<maxm;i++) for(int j = i;j<=i+pow_num-1;j++) ans = (ans+(T[j]*powp[j-i]%mod))%mod;
printf("%lld\n",ans);
return 0;
}
