| Time Limit: 3000MS | Memory Limit: 131072KB | 64bit IO Format: %lld & %llu |
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。
Source
SDOI2012
求Σgcd(i,n) (1<=i<=n)
暴力枚举当然可行，但是TLE不可避。
考虑转化问题，从1到n的范围内，有许多个i的gcd(i,n)等于同一个n的因数。我们可以枚举n的每一个因数k，累计“以该数k为解的gcd(i,n)的个数s(k)"乘以该数，就能得到答案。
若有gcd(n,m)=k，那么n和m同除公约数k后，可以得到gcd(n/k,m/k)=1。由前式可知(m/k)与(n/k)互质。满足条件的(m/k)个数，也就是s(k)就等于phi(n/k) ←欧拉函数！
解1：直接套模板。算法无误，但是因为题目数据大，保存函数后再处理会RE（原因目测是存储用数组开不了那么大）
/*by SilverN*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=;
long long n;
int m[maxn],phi[maxn],p[maxn],pt;
int euler()
{
phi[]=;
int N=maxn;
int k;
for(int i=;i<N;i++)
{
if(!m[i])//i是素数
p[pt++]=m[i]=i,phi[i]=i-;
for(int j=;j<pt&&(k=p[j]*i)<N;j++)
{
m[k]=p[j];
if(m[i]==p[j])//为了保证以后的数不被再筛，要break
{
phi[k]=phi[i]*p[j];
/*这里的phi[k]与phi[i]后面的∏(p[i]-1)/p[i]都一样（m[i]==p[j]）只差一个p[j]，就可以保证∏(p[i]-1)/p[i]前面也一样了*/
break;
}
else
phi[k]=phi[i]*(p[j]-);//积性函数性质，f(i*k)=f(i)*f(k)
}
}
}
int main(){
euler();
scanf("%lld",&n);
long long m=sqrt(n);
int i,j;
long long ans=;
for(i=;i<=m;i++){
if(n%i==){
ans+=phi[n/i]*i;
ans+=(n/i)*phi[i];
}
}
printf("%lld\n",ans);
return ;
}
解2：多花点时间，每次都算一遍。并不会TLE，神奇
代码是从hzw学长那学到的，精简得很。
/*by SilverN*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int mxn=;
long long n,m;
long long phi(long long x){
long long a=x;
for(long long i=;i<=m;i++){
if(x%i==){//找到因数
a=a/i*(i-);//基本计算公式 a*=((i-1)/i)
while(x%i==)x/=i;//除去所有相同因数
}
}
if(x>)a=a/x*(x-);//处理最后一个大因数
return a;
}
int main(){
scanf("%lld",&n);
m=sqrt(n);
int i,j;
long long ans=;
for(i=;i<=m;i++){
if(n%i==){
ans+=phi(n/i)*i;
ans+=(n/i)*phi(i);
}
}
printf("%lld\n",ans);
return ;
}