ez problem 4
luogu_gza
·
·
算法·理论
我发 ez problem 5 的时候犇犇里面提了一嘴 4 去哪里了，其实在这里。
来源：2026 西安区域赛 I。
您可以前往 https://qoj.ac/problem/20059 观看题面。
::::info[solution]
令 s_i=\frac{i(i-1)}{2}，令 cnt_{d,j}=\sum_{i=1}^{n}[s_i \bmod d=j]，则能被 d 整除的方案数是 f(d)=\sum_{i=0}^{d-1}\binom{cnt_{d,i}}{m}，显然 d|\frac{n(n-1)}{2}。
因此我们尝试计算答案的质因数分解结果，不难得到答案在 p 上的次数是 \sum_{k \geq 1}f(p^k)。
若 p=2，令 d=2^t。显然 s_i 有 2d 的周期。
有了这个结论后我们就不难得出：
+ 若 $n \bmod 2d=0$，则 $f(d)=d\binom{2\lfloor \frac n{2d} \rfloor}{m}$。
+ 若 $n \bmod 2d=1$，则 $f(d)=(d-1)\binom{2\lfloor \frac n{2d} \rfloor}{m}+\binom{2\lfloor \frac n{2d} \rfloor+1}{m}$。
---
若 $p$ 为奇质数，令 $d=p^t$，$s_i$ 有 $d$ 的周期，令 $g(n)=\sum_{i=0}^{d-1}[i^2 \equiv n \pmod d]$，有 $f(d)=\sum_{j=0}^{d-1} \binom{\lfloor \frac nd \rfloor g(j)+[j=1 \land n \bmod d=1]}{m}$。上指标的修正是平凡的，我们可以先丢掉这个修正。
做一些平凡的观察，$g(0)=p^{\lfloor \frac t2 \rfloor}$。其他有值的 $g(n)$ 都满足 $n=Ap^B$，其中 $\gcd(A,p)=1$，$B \bmod 2=0$ 且 $A$ 存在二次剩余，此时 $g(n)=2p^{\frac B2}$，对于一个 $B$ 来说这样的 $n$ 一共有 $\frac{(p-1)}{2}p^{t-B-1}$ 个，可以计算。
补个这个结论的证明。
#### $g(n)=2p^{\frac B2}
有同余方程 y^2 \equiv n=Ap^B \pmod {p^t}，若 y 是解则 v_p(y^2)=v_p(n)=B，因此 v_p(y)=\frac B2。令 y=p^{\frac B2}z，有 p \nmid z，代入原方程有 z^2 \equiv A \pmod {p^{t-B}}，由 Hensel 引理有这个方程恰有两个解，为 z_0 和 -z_0。它们模 p^{t-B} 不相等，因为 p 是奇数。但是我们要求的是 \bmod p^t 的解 y 的个数，有 y=p^{\frac B2}(z+kp^{t-B})=p^{\frac B2}z+kp^{t-\frac B2}，因此对于每个 z 对应着 p^{\frac B2} 个 y，而 z 本身有两个解，因此 g(n)=2p^{\frac B2}。
这样的 n 一共有 \frac{(p-1)}{2}p^{t-B-1} 个
由于 n=Ap^B，模 p^t 下 n 只依赖于 A \bmod p^{t-B}，因此问题转化为了求模 p^{t-B} 中与 p 互质且是模 p 二次剩余的剩余类个数。
乘法群 (\mathbb{Z}/p^{t-B}\mathbb{Z})^{\times} 的阶是 \varphi(p^{t-B})=(p-1)p^{t-B-1}。在这个群中，平方剩余构成一个子群，其大小为阶的一半，因此剩余类个数为 \frac{(p-1)}{2}p^{t-B-1}，这样的 n 也一共有这样的个数。
我们现在这些组合数都是在指数上的，所以要对 10^9+122 取模，10^9+122=2 \times 3 \times 11 \times 2089 \times 7253，用 CRT 合并计算即可。
还要注意 mod|\frac{n(n-1)}{2} 的情形。
::::