啥都不会只能学数论QAQ
原题：
Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。
0<N<=2^32
恩
先知道是欧拉函数，然后照着反演推了半天，越推越鬼畜，然后gg看题解……
数论嘛，推公式：
对就这么简单
然后O(√n)求欧拉函数即可，其实就是用通式暴力计算……φ(x)=x*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…..(1-1/pn)
注意暴力计算的时候不能用积性性质，因为欧拉函数的积性要求互质
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 #define ll long long 8 ll n,m; 9 ll phi(ll x){ 10 ll tmp=x; 11 for(int i=2;i<=m;++i)if(!(x%i)){ 12 tmp=tmp/i*(i-1); 13 while(!(x%i)) x/=i; 14 } 15 if(x>1) tmp=tmp/x*(x-1); 16 return tmp; 17 } 18 int main(){//freopen("ddd.in","r",stdin); 19 cin>>n; 20 m=(ll)sqrt(n*1.0); 21 ll ans=0; 22 for(int i=1;i<=m;++i)if(!(n%i)){ 23 ans+=(ll)i*phi(n/i); 24 if(i*i<n) ans+=(ll)(n/i)*phi(i); 25 } 26 cout<<ans<<endl; 27 return 0; 28 }