单位根反演
单位根反演
单位根的定义此处不再赘述，根据单位根的相关性质，我们可以得到：
$$
[m \mid i] = \frac 1m \sum_{k=0}^{m-1} \omega_{m}^{ki}
$$
证明如下：
考虑等比数列求和 $S= \dfrac{\omega_m^{im}-1}{\omega_m^i -1}$，当 $m \nmid i$ 的时候，分子为 $0$，分母不为 $0$，$S=0$；当 $m \mid i$ 的时候，分母为 $0$，需要特判，这个时候 $\omega_{m}^{ki}=1$，所以 $S=1$，得证。
例题
转化后，题意变为求出在 $[1,n]$ 内选出若干个数，和是 $m$ 的倍数的选数方案。其中 $m \mid n$，$1 \le n \le 10^{18}$，$1 \le m \le 10^7$，多测 $T \le 10^4$。
解法
首先设 $f(x)=(1+x)(1+x^2)\dots(1+x^n)$，设其展开后的式子为 $a_0+a_1x+a_2x^2+\dots+a_kx^k$，那么答案就是 $\sum_{m \mid i} a_i$。
因为前面提到 $[m \mid i] = \frac 1m \sum_{k=0}^{m-1} \omega_{m}^{ki}$，所以答案就是 $\sum_{i=0}^{m-1} f(\omega_m^i)$。
问题转化为如何快速计算该式子。
当 $m$ 为奇质数的时候，根据单位根的定义，我们对于 $z^m-1$ 在复数域上进行分解有 $z^m-1=(z-\omega_m^{1})(z-\omega_m^2)\dots(z-\omega_m^m)$，带入 $z=-1$，得到 $(1+\omega_m^1)(1+\omega_m^2)\dots(1+\omega_m^m)=2$，因为 $m$ 是奇质数，所以 $(1+\omega_m^{i})(1+\omega_m^{2i})\dots(1+\omega_m^{mi})=2$。
当 $m$ 为偶数的时候同理等于 $0$。
又因为 $m \mid n$，所以：$f(\omega_m^i) = 2^{\frac nm}$，当 $i=0$ 的时候需要特判，答案为 $2^n$，所以 $\sum_{i=0}^{m-1} f(\omega_m^i)=\frac 1m((m-1)2^{\frac nm}+2^n)$。
如果 $m$ 不是奇质数又怎么办呢，设 $(i,m)=p$，那么 $i \sim mi$ 按照模 $m$ 分成 $((1+\omega_m^p)(1+\omega_m^{2p})\dots(1+\omega_m^m))^{p}$，所以 $f(\omega_{m}^i)=((1+\omega_m^p)(1+\omega_m^{2p})\dots(1+\omega_m^m))^{p \frac nm}$。
因为单位根有 $\omega_{bk}^{ak}=\omega_b^a$，所以 $f(\omega_{m}^i)=((1+\omega_{\frac mp}^1)(1+\omega_{\frac mp}^{2})\dots(1+\omega_{\frac mp}^{\frac mp}))^{p \frac nm}$，根据上文，如果 $\frac mp$ 是偶数，那么结果为 $0$，否则结果为 $2$。
所以式子变成：
$$
\frac 1m(\sum_{i=0}^{m-1} 2^{p \frac nm}[2 \nmid \frac mp])
$$
注意到 $i=0$ 的答案恰好就是 $2^n$，因此不需要特判。
因为 $2 \nmid \frac mp$，我们发现如果设 $m=2^k \times u$，$k$ 最大，那么只有 $i=2^k \times q$ 的时候 $2 \nmid p$，所以直接枚举 $q \le u$，得到：
$$
\begin{aligned}
\frac 1m(\sum_{i=0}^{m-1} 2^{p \frac nm}[2 \nmid \frac mp]) &= \frac 1m(\sum_{i=1}^{u}2^{\frac{n}{2^ku}\gcd(2^ku,2^ki)}) \
&= \frac 1m(\sum_{i=1}^{u}2^{\frac{n}{u}\gcd(u,i)}) \
\end{aligned}
$$
于是考虑枚举 $\gcd(u,i)=d$，则：
$$
\frac 1m(\sum_{d \mid u}2^{\frac nu d} \varphi(\frac ud))
$$
因为 $u$ 不含 $2$ 因子，所以 $u$ 的因数特别少，直接枚举即可，时间复杂度就是 $O(Td(u))$，$d(u)$ 可能大概在 $200$ 左右。
代码
代码如下，仅供参考：
1 |
|