自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 22:30:21，当前版本为作者最后更新于2021-04-06 13:20:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

推式子。

首先 $n$ 为偶数时 $1+e^{\frac{2\pi i\cdot (\frac{n}{2})\cdot (1)^{t-1}}{n}}=0$，故答案为 $0$。

下面看 $n$ 为奇数。考虑取 $\log$ 将乘积转化成求和，打些小数据从样例 1 猜结论发现答案基本都是 $2$ 的幂。令 $f(n,t)=\log_2\left(\prod_{x_1=1}^{n}\prod_{x_2=1}^{n}\dots\prod_{x_t=1}^{n}\left( 1+e^{\frac{2\pi ix_1x_2\dots x_t}{n}} \right)\right)$。

设 $\omega=e^{\frac{2\pi i}{n}}$。首先有 $\prod\limits_{x=1}^{n}\left( u-\omega^x \right)=u^n-1$， $\prod\limits_{x=1}^{n}\left( 1+e^{\frac{2\pi ix}{n}} \right)=(-1)^n\cdot((-1)^n-1)=2=2^1$。故 $f(n,1)=1$。

其他时候我们考虑处理 $x_1$，当 $\gcd(x_1,n)=d,x_1=dy,n=dm$ 时，

$$\begin{aligned} \prod_{x_2=1}^{n}\dots\prod_{x_t=1}^{n}\left( 1+e^{\frac{2\pi ix_1x_2\dots x_t}{n}} \right)&=\prod_{x_2=1}^{n}\dots\prod_{x_t=1}^{n}\left( 1+e^{\frac{2\pi iyx_2\dots x_t}{m}} \right)\\ &=\left(\prod_{x_2=1}^{m}\dots\prod_{x_t=1}^{m}\left( 1+e^{\frac{2\pi ix_2\dots x_t}{m}} \right)\right)^{d^{t-1}}\\ &=2^{d^{t-1}f(m,t-1)}, \end{aligned}$$

故（$d=\gcd(x,n),m=\dfrac{n}{d}$，下同）

$$\begin{aligned} f(n,t)&=\sum_{x=1}^{n}d^{t-1}f(m,t-1)\\ &=\sum_{d|n}\sum_{\gcd(x,n)=d}d^{t-1}f(m,t-1)\\ &=\sum_{d|n}\varphi(m)d^{t-1}f(m,t-1), \end{aligned}$$

显然当 $f(n,t-1)$ 积性时 $f(n,t)$ 也积性。

那么就只要对 $n$ 分解质因子，求出每个 $f(p^v,t)$。

Pollard-Rho 分解质因数然后直接递推即可，时间复杂度 $O(n^{\frac{1}{4}}+k\max\{v\})$。