【欧拉函数】acwing221
传送门
解法：欧拉函数
俗话说数论上来先打表，打完表智力就正常了
我先打了一张n为50的表
//1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2 25 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 50
发现gcd好像有很多重复的数字
gcd为1的就是与50互质的数，个数为\phi{(N)}个
gcd为2的个数怎么算？仔细想想，对于每一个gcd(i,N) = d的数对，都存在gcd(i/d , N/d) = 1
也就是说，对于每个数对，各自除以gcd和N都是互质的，那么很明显数对的个数为\phi{(N/d)}
有了以上结论，可以想到，N的所有gcd的可能性就是N的所有约数，对于每个约数，数对的个数为\phi{(N/d)}个，它们的和就是d\phi{(N/d)}。
进一步总结，答案就是\sum_{d|N}d\phi{(N/d)}
这个函数是两个积性函数的迪利克雷卷积，所以是个积性函数，有xxxx的性质，可以线筛等等
然而我一看数据范围2^31那比不可能线筛，只能暴力算了。… Read the rest