BZOJ 2705([SDOI2012]Longge的問題-歐拉函數φ(i))

2705: [SDOI2012]Longge的問題
Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 375  Solved: 239
[Submit][Status][Discuss]
Description
Longge的數學成績非常好，並且他非常樂於挑戰高難度的數學問題。現在問題來了：給定一個整數N，你需要求出∑gcd(i, N)(1<=i <=N)。
Input
一個整數，為N。
Output
一個整數，為所求的答案。
Sample Input
6

Sample Output
15

HINT

【數據范圍】

對於60%的數據，0<N<=2^16。

對於100%的數據，0<N<=2^32。

歐拉函數：

枚舉n的約數k，令s(k)為滿足gcd(m,n)=k,(1<=m<=n)  m的個數，則ans=sigma(k*s(k)) (k為n的約數）

 因為gcd(m,n)=k,所以gcd(m/k,n/k)=1,於是s(k)=euler(n/k)

 枚舉n的約數即可，復雜度o(sqrt(n))

PS:剛剛ksy告訴我C++，直接讀int比讀char轉int慢（——0）

[cpp]
#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<cmath>  
#include<functional>  
#include<algorithm>  
#include<cctype>  
#include<iostream>  
using namespace std; 
#define MAXN (2<<31)  
long long ans=0,n; 
long long phi(long long n) 
{ 
    if (n==1) return 1; 
//  cout<<n;  
    long long ans=1; 
    for (long long i=2;i*i<=n;i++) 
        if (n%i==0) 
        { 
            int k=0; 
            while (n%i==0) {k++,n/=i;} 
            ans*=i-1; 
            for (int j=2;j<=k;j++) ans*=i;        
        } 
    if (n>1) ans*=n-1; 
//  cout<<' '<<ans<<endl;  
    return ans; 
} 
int main() 
{ 
    cin>>n; 
    for (int i=1;i*i<=n;i++) 
        if (n%i==0) 
        { 
            ans+=(long long)i*phi(n/i); 
            if (i*i<n) ans+=(long long)n/i*phi(i);        
        } 
    cout<<ans<<endl; 
    return 0; 
} 

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
#include<iostream>
using namespace std;
#define MAXN (2<<31)
long long ans=0,n;
long long phi(long long n)
{
 if (n==1) return 1;
// cout<<n;
 long long ans=1;
 for (long long i=2;i*i<=n;i++)
  if (n%i==0)
  {
   int k=0;
   while (n%i==0) {k++,n/=i;}
   ans*=i-1;
   for (int j=2;j<=k;j++) ans*=i;   
  }
 if (n>1) ans*=n-1;
// cout<<' '<<ans<<endl;
 return ans;
}
int main()
{
 cin>>n;
 for (int i=1;i*i<=n;i++)
  if (n%i==0)
  {
   ans+=(long long)i*phi(n/i);
   if (i*i<n) ans+=(long long)n/i*phi(i);  
  }
 cout<<ans<<endl;
 return 0;
}