啥都不会只能学数论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
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            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