【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; }