【51nod1040】【最大公约数之和】【欧拉函数】

题目大意

给出一个n，求1-n这n个数，同n的最大公约数的和。比如：n = 6

1,2,3,4,5,6 同6的最大公约数分别为1,2,3,2,1,6，加在一起 = 15

解题思路

ans=∑x|nx∗∑ni=1gcd(i,n)==x

=> ans=∑x|nx∗∑ni=1gcd(i/x,n/x)==x

=> ans=∑x|nx∗fai(n/x)

可以用sqrt（n）的时间枚举因子x，再用sqrt（x）的时间分解质因数， fai(x)=x∑p|x1−1/p 。

#include<cmath>
#include<cstdio>
#include<algorithm>
#define LL long long
#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a>b)?a:b)
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
int const maxn=1e9;
int n;
int fai(int x){
int res=x,tmp=x;
for(int i=2;i*i<=x;i++)
if(x%i==0){
            res=res/i*(i-1);
while(x%i==0)x=x/i;
        }
if(x!=1)res=res/x*(x-1);
return res;
}
int main(){
    scanf("%d",&n);
int mx=sqrt(n);LL ans=0;
    fo(i,1,mx)
if(n%i==0)
            ans+=1ll*i*fai(n/i)+1ll*n/i*fai(i);
if(mx*mx==n)ans-=1ll*mx*fai(mx);
printf("%lld",ans);
return 0;
}