南外集训 2024.1.19 T3

给定正整数 \(m, n\) 使得 \(m|n\)，求 \([1, n]\cap\mathbb Z\) 的所有子集中有多少和是 \(m\) 的倍数。

\(1\le T\le 10^4, 1\le m\le 10^7, 1\le n\le 10^{18}\)

相当于求 \(F(z) = (1 + z^0)(1+z^1)\dots (1+z^{n-1})\) 的 \(0, m, 2m,\dots\) 项之和。单位根反演可得 \(Ans = \sum\limits_{i=0}^{m-1}F(\omega_m^i)\)。如果 \(\gcd(i, m) = 1\)，则 \(F(\omega_m^i) = \left(\prod\limits_{j=0}^{m-1}(1+\omega_m^j)\right)^\frac{n}{m}\)，注意到 \(z^m-1 = \prod\limits_{j=0}^{m-1}(z-\omega_m^j)\)，代入 \(z = -1\) 易得当 \(m\) 为奇数时上式为 \(2^\frac{n}{m}\)，否则为 \(0\)。

对于 \(\gcd(i, m)\ne 1\) 的情况，不妨设 \(\gcd(i, m) = g\)，则 \(F(\omega_m^i) = \prod\limits_{t=0}^{g-1}\left(\prod\limits_{j=0}^{\frac{m}{g}-1}(1+\omega_\frac{m}{g}^j)\right)^\frac{n}{m} = [2\not\mid\frac{m}{g}]2^\frac{ng}{m}\)。所以我们实际上只关心 \(gcd(i, m)\)，那么考虑枚举所有 \(m\) 的约数 \(d\)，容易发现与 \(m\) 的 \(\gcd\) 为 \(d\) 的总共有 \(\varphi(\frac{m}{d})\) 个。预处理出所有 \(\varphi\)，暴力分解 \(m\) 的质因子（可以筛出素数，单次分解时间复杂度为 \(\Theta(\frac{\sqrt{m}}{\ln m})\)），于是做完了。