题目链接
补档文。
题意简述
对质数 \(p\)，记 \(N(p, q) = \sum_{n = 0}^q T_n \cdot p^n\)，其中 \(T_n\) 由以下随机数生成器给出：
\(S_0 = 290797\)
\(S_{n + 1} = S_n^2 \bmod 50515093\)
\(T_n = S_n \bmod p\)
记 \(\operatorname{NF}(p, q)\) 为 \(\operatorname{N}(p, q)\) 的阶乘中因子 \(p\) 的次数。求 \(\operatorname{NF}(61, 10^7) \bmod 61^{10}\)。
题目解答
由 Legendre 公式，答案由下式给出：
\[\begin{aligned}
NF(p, q) & = \sum_{i=1}^{\infty} \left\lfloor \dfrac{\sum_{j=0}^{q} T_j \cdot p^j}{p^i} \right\rfloor \\
& = \sum_{i=1}^{\infty} \left\lfloor \sum_{j=0}^{q} T_j \cdot p^{j-i} \right\rfloor \\
& = \sum_{i=1}^{\infty} \left\lfloor \color{Red}{\sum_{j=i}^{q} T_j \cdot p^{j-i}} \color{Black} + \color{Blue}{\sum_{j=0}^{i-1} T_j \cdot p^{j-i}} \right\rfloor
\end{aligned}
\]
对于蓝色部分，由于题中的定义，显然有 \(0 \leq T_i \leq p-1\)。故：
\[\begin{aligned}
\sum_{j=0}^{i-1} T_j \cdot p^{j-i} & \leq (p-1) \sum_{j=0}^{i-1} p^{j-i} \\
& = (p-1) \sum_{j=-i}^{-1} p^{j} \\
& = (p-1) \dfrac{p^{-i}(1-p^i)}{1-p} \\
& = 1 - p^{-i} < 1
\end{aligned}
\]
且 \(\sum_{j=0}^{i-1} T_j \cdot p^{j-i} \geq 0\)。
而对于红色部分，显然它是一个整数。故由高斯函数的定义有：
\[\begin{aligned}
NF(p, q) & = \sum_{i=1}^{\infty} \left\lfloor \color{Red}{\sum_{j=i}^{q} T_j \cdot p^{j-i}} \color{Black} + \color{Blue}{\sum_{j=0}^{i-1} T_j \cdot p^{j-i}} \right\rfloor \\
& = \sum_{i=1}^{\infty} \color{Red}{\sum_{j=i}^{q} T_j \cdot p^{j-i}} \\
\end{aligned}
\]
虽然第一个求和的上限是 \(+\infty\)，但显然对于任意 \(i > q\)，这个 \(i\) 并没有贡献，不必担心。
由于存在 \(j\) 的单项，考虑交换两个求和的位置，计算贡献后有：
\[\begin{aligned}
NF(p, q) & = \sum_{i=1}^{\infty} {\sum_{j=i}^{q} T_j \cdot p^{j-i}} \\
& = \sum_{j=1}^{q} \left( T_j {\sum_{i=0}^{j-1} p^{i}} \right)\\
\end{aligned}
\]
注意到题目的模数 \(61^{10} = p^{10}\)，所以 \(p^{i}\) 只有在 \(i \leq 9\) 时有贡献，否则 \(i \geq 10\) 时模 \(61^{10}\) 一定为 0。
故：
\[\begin{aligned}
NF(p, q) & = \sum_{j=1}^{q} \left( T_j {\sum_{i=0}^{\min(j-1, 9)} p^{i}} \right)\\
\end{aligned}
\]
据此计算即可，时间复杂度 \(\mathcal{O}(q)\)。