自动搬运

查看原文

来自洛谷，原作者为

	Argon_Cube So now I am trapped in my Eternal Subconscienc∃.

搬运于2025-08-24 22:30:33，当前版本为作者最后更新于2024-10-04 19:29:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

巨大推式子题又何尝不是一种数学大模拟呢。

来一个不一样的，应该简单一些的做法。

---

首先 $x^n-1=\prod_{0\leq i<n}(x-\omega_n^i)$，代入 $x=-1$ 就得到

$$\prod_{i=0}^{n-1}(1+\omega_n^i)=1-(-1)^n=2[2\nmid n] $$

所以首先 $2|n$ 时输出 $0$。否则直接展开最后一层：

$$\prod_{0\leq x_1,\cdots,x_{t-1}<n}2^{\gcd\left(\prod_{0<i<t}x_i,n\right)} $$

相当于是要对 $0\leq m<k$ 求

$$f(n,m)=\sum_{0\leq x_1,\cdots,x_{m}<n}\gcd\left(\prod_{1\leq i\leq m}x_i,n\right)\mod 335544322 $$

发现 $335544322=2\times 167772161$，后面的是知名 NTT 模数，前面那个 $2$ 我们到时候再处理。显然 $f(n,0)=1$，以下我们默认 $m>0$ 不然会很麻烦。

显然这个式子就是 ABC245Ex，所以直接把那题方法套过来，首先跟 ABC245Ex 一样 $f(n,m)$ 是积性的，也就是说如果 $\gcd(a,b)=1$ 则 $f(ab,m)=f(a,m)f(b,m)$，证明就直接 CRT，所以我们直接把 $a$ 用 Pollard-Rho 质因数分解一下就只用考虑怎么计算 $f(p^n,m)$ 就行了。

算 $f(p^n,m)$ 就是枚举一下 $0\leq i<n$ 算出 $\gcd(\prod x,p^n)=p^i$ 有几种情况，剩下的就是 $\gcd(\prod x,p^n)=p^n$ 的方案数。计算 $\gcd(\prod x,p^n)=p^i$ 的方案数也和 ABC245Ex 一样，先让每个位置随便取与 $p$ 互质的数，然后把这 $i$ 个 $p$ 分到某些位置上，某个位置多分到一个 $p$ 这个地方取数的方案数就要除以 $p$，这样如果数组长为 $m$ 方案数就是 $\binom{m-1+i}{i}(p-1)^mp^{m(n-1)-i}$。

所以最后我们得到 $f(p^n,m)$ 是这坨东西：

$$f(p^n,m)=p^{n(m+1)}+\binom{m+n-1}{m}(p-1)^mp^{m(n-1)}-(p-1)^mp^{n+m(n-1)}\sum_{i=0}^{n-1}\binom{m-1+i}{i}p^{-i} $$

第一项是总方案数乘上 $p^n$，第三项是算有多少种方案 $\gcd\neq p^n$，它们的贡献在第一项里被算成了 $p^n$ 要减掉，第二项是 $\gcd\neq p^n$ 的方案的贡献。

发现 $f(p^n,m)$ 一定是个奇数，所以模 $2$ 的结果算出来了！这样我们只需要解决 $p_{mod}=167772161$ 就可以合并了，具体来说结果是偶数就加上一个 $167772161$ 即可。

现在要先讨论 $p\bmod p_{mod}$ 为 $0$ 或 $1$ 的情况，因为我们以后要算 $p^{-1}$ 和 $(p-1)^{-1}$，如果出现了这种情况那么 $f(p^n,m)\equiv p\pmod{p_{mod}}$。

现在已经能过原版了，要解决加强版要快速算后面那个和式：

$$g_m=\sum_{i=0}^{n-1}\binom{m-1+i}{i}p^{-i}$$

直接把中间那个二项式用加法公式拆了解出 $g_{m+1}$ 就可以得到

$$g_{m+1}=\frac{p}{p-1}\left(g_m-\binom{m+n-1}{m}p^{-n}\right) $$

发现这个东西可以直接线性递推就做完了，复杂度 $\Omicron(\sqrt[4]a+(k\log(bkp_{mod}))\omega(a)+k\log p_{mod})$。