进教室

wjh15101051's space

卧薪尝胆，厚积薄发。

进教室

Date: Thu Oct 18 09:27:27 CST 2018

In Category: NoCategory

Description：

求： $$ \prod_{i=1}^n\prod_{j=1}^n\gcd(i,j) $$ $1\leqslant testcases\leqslant10^7,1\leqslant n\leqslant 10^6$

Solution：

类似仪仗队那题的做法，可以把答案看成一个矩阵，然后发现矩阵是对称的，所以：

$$ \begin{align} 原式&=\prod_{i=1}^n\prod_{j=1}^i\gcd(i,j)\times2-n! \end{align} $$

这样中心就变成了求： $$ \prod_{i=1}^n\prod_{j=1}^i\gcd(i,j) $$ 然后有一个比较神奇的转化，就是把矩阵按行考虑，也就是设： $$ g[n]=\prod_{i=1}^n\gcd(i,n) $$ 然后： $$ g[n]=\prod_{i=1}^n\gcd(i,n)=\prod_{d|n}d^{\begin{align}\sum_{i=1}^n[\gcd(i,n)=d]\end{align}}=\prod_{d|n}d^{\varphi(\frac n d)} $$ 这样就可以先枚举 $d$ ，然后枚举 $d$ 的倍数，由调和级数得复杂度是 $O(n\ln n)$ 的，然后再求个前缀和就可以 $O(1)$ 回答询问了。

In tag: 数学-莫比乌斯反演

wjh15101051