C 兰亭序 题解

· · 题解

推式子。

首先 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 时，

\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}，下同）

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\})。