51nod 1594 Gcd and Phi(莫比乌斯反演)
题目链接
传送门
思路
如果这题是这样的：
\[F(n)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\phi(gcd(i,j)) \]那么我们可能会想到下面方法进行反演：
\[\begin{aligned} F(n)=&\sum\limits_{k=1}^{n}\phi(k)\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[gcd(i,j)=k]&\\ =&\sum\limits_{k=1}^{n}\phi(k)\sum\limits_{i=1}^{\frac{n}{k}}\sum\limits_{j=1}^{\frac{n}{k}}[gcd(i,j)=1]&\\ \end{aligned} \]令\(f(n)\)为\(gcd(i,j)=n\)的有序对的对数，\(g(n)\)为\(gcd(i,j)=n\text{和}n\)的倍数的有序对的对数，则
\[\begin{aligned} &g(n)=\sum\limits_{n|d}f(d)&\\ \rightarrow&f(n)=\sum\limits_{n|d}\mu(\frac{d}{n})g(d)& \end{aligned} \]然后将\(f(1)=\sum\limits_{i=1}^{n}\mu(i)g(i)\)代入\(F(n)\)得到\(F(n)=\sum\limits_{k=1}^{n}\phi(k)\sum\limits_{i=1}^{\frac{n}{k}}\mu(i)g(i)\)，然后先预处理\(\sum\limits_{i=1}^{\frac{n}{k}}\mu(i)g(i)\)，然后暴力枚举\(k\)或者数论分块求解答案就可以了，这里有几道类似的，有兴趣的可以做一下。
但是这题却不是我们所希望的那种形式，那么该怎么办呢？我们发现\(n\)小于等于\(2e6\)，那么我们可以记录一下每个数的\(\phi\)是多少，然后记录一下每个\(\phi\)出现的次数后就可以转换成上述题意了(这个思想昨天的\(CCPC\)网络赛1010也用到了，不过这题由于后面不会处理就没补了23333)，假设\(c_i\)表示\(\phi=i\)的个数，那么求解的式子就变成了
\[F(n)=\sum\limits_{k=1}^{n}\phi(k)\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}c_ic_j[gcd(i,j)=k] \]令\(f(n)\)为\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}c_ic_j[gcd(i,j)=n]\)，\(g(n)\)为\(为和的倍数\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}c_ic_j[gcd(i,j)\text{为}n\text{和}n\text{的倍数}]\)，则
\[\begin{aligned} g(n)=&\sum\limits_{n|i}\sum\limits_{n|j}c_ic_j&\\ =&\sum\limits_{i=1}^{n}c_i\sum\limits_{j=1}^{n}c_J&\\ =&(\sum\limits_{i=1}^{n}c_i)^2&\\ =&\sum\limits_{n|d}f(d)& \end{aligned} \]那么
\[f(n)=\sum\limits_{n|d}\mu(\frac{d}{n})g(d) \]最后答案为
\[F(n)=\sum\limits_{k=1}^{n}\phi(k)f(k) \]然后暴力枚举\(k\)求解即可。
代码
#include
#include