Longge的数学成绩非常好,并且他非常乐于挑战高难度的数学问题.现在问题来了:给定一个整数N,你需要求出∑gcd(i N)(1<=i <=N).
枚举n的因子,对于一个因子x,求与n只有这一个因子x的数目,显然如果暴力的话就是for(int i=x;i<=n;i+=x)然后判断每个i是否与n只有一个因子,从而求得数目然后乘上x.
可以用欧拉函数简化这一过程,因子为x,那么与他成对那个就是y=n/x.我们只需求出小于y并与y互质的数目就可以了,因为与y互质,那么与k*y(显然ky可以等于n)仍然互质,也就是说找出来的每个z.必定满足gcd(nz)==1且z*x<n,那么gcd(nz*x)肯定就只有x这一个因子了,从而简化了过程
LL ans=0;
if(n%i==0)