题解 P1390 【公约数的和】
VengefulSpirit · · 题解
本题是一道标准的数论题，所以一切爆搜都走远了。。。
正解：
设f(n)=gcd(1,n)+gcd(2,n)+gcd(3,n)+...+gcd(n-1,n)，
则结果为f(2)+f(3)+...+f(n)
由于所有gcd(x,n)的值都是n的约数，可以按这个约数分类。
用g(n,i)表示满足gcd(x,n)=i且x<n的正整数x的个数，则有
f(n)=Σ{g(n,i)*i|i为n的约数}.
由于gcd(x,n)=i的充要条件是(x/i)与(n/i)互质，因此满足条件的(x/i)有φ(n/i)个
因此：g(n,i)=φ(n/i).
故: [u]f(n)=Σ{φ(n,i)*i|i为n的约数}[/u]
如果依次计算f(n)，需要枚举每个n的约数i，速度较慢。而把思维逆转，对于每个i枚举其倍数n，更新f(n)的值，时间复杂度将与素数筛法同阶。
注1：f()这个数组是便于同学们理解此算法，程序中不一定需要出现->这一点自行脑补。
注2：φ()为欧拉函数，不懂的同学自行百度它的定义及生成。
注3：一些初中同学AC算法我没有看懂，目测是变形的欧拉，本质应该是一样的。