C. 最大公约数

求 \(\sum\limits_{i=1}^n\dfrac{n}{gcd(i,n)}\)。

先考虑用欧拉函数解决。考虑枚举 \(d=\gcd(i,n)\) 的取值。式子变成 \(\sum\limits_{d\mid n}\sum\limits_{i=1}^n[\gcd(i,n)=d]\cdot\dfrac{n}{d}\)。

对于 \(\gcd(a,b)=d\)，有 \(\gcd(\frac{a}{d},\frac{b}{d})=1\)。

所以 \(\sum\limits_{d\mid n}\sum\limits_{i=1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1]\cdot\dfrac{n}{d}\)。

而明显，在 \(\frac{n}{d}\) 中与它互质的数即为 \(\varphi(\frac{n}{d})\)。

\(\sum\limits_{d\mid n}\dfrac{n}{d}\cdot\varphi(\frac{n}{d})\)

\(=\sum\limits_{d\mid n}d\cdot\varphi(d)\)

设 \(f(n)=\sum\limits_{d\mid n}d\cdot\varphi(d)\)，可以证明，\(f(n)\) 是积性函数。

证明：

\(\because\gcd(a,b)=1\)

\(\therefore\) \(ab\) 的因子一部分来自 \(a\)，一部分来自 \(b\)。

\(f(ab)=\sum\limits_{d\mid ab}d\cdot\varphi(d)=\sum\limits_{d\mid a}\sum\limits_{d'\mid b}dd'\cdot\varphi(dd')\)

又 \(\because \varphi(dd')=\varphi(d)\varphi(d')\)

\(f(ab)=\sum\limits_{d\mid n}d\cdot\varphi(d)\sum\limits_{d'\mid n}d'\cdot\varphi(d')=f(a)f(b)\)

证毕。

直接线性筛计算积性函数即可。

关于如何计算，设 \(x=i\times pri_j\)：

1. 当 \(i\) 是质数时，\(f(i)=i\times(i-1)+1\)；

2. 当 \(pri_j\mid i\) 时，分两种情况，\(i\) 不是最小质因数的幂次，\(f(x)=f(low_x)f(x/low_x)\)，\(low_x\) 为 \(x\) 的最小质因数的最大幂次；\(i\) 是小质因数的幂次，一般有规律可以计算，因为因数易知，比如这里就可以写成 \(f(x)=f(i)+pri_j\cdot\varphi(pri_j)\)。

3. 当 \(pri_j\nmid i\) 时，\(f(x)=f(i)f(pri_j)\)。

总结：此类题的思路就是先化简式子，先看看能不能有欧拉函数做，再考虑莫反。最后证明此函数是积性函数，直接线性筛预处理做到 \(O(n)\) 多次询问。