1.题目

biubiu

2.题解

这题不能直接预处理出phi,因为数组开不下。。

设gcd(i,n)==k ->gcd(i/k,n/k)==1 。

所以i/k有phi[n/k]种选法 。

ans=sigma(phi[k])1<=k<=n;

还是过不了。。。

设f[d]为gcd(i,n)==d的方案数,d是n的约数

ans=sigma(d×f[d]) !

枚举约数d,可以在sqrt(d)内求phi(d)

代码: