记录编号	600722	评测结果	AAAAAAAAAA
题目名称	[河南省队2012] 最大公约数和	最终得分	100
用户昵称	xxz	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2025-05-12 20:06:29	内存使用	3.84 MiB

#include<bits/stdc++.h>
#define ll long long

ll n,t,ans,prime[200000];
bool flag[1000000];
long long ou(ll k){
	ll i,s=k,tmp=k;
	for(i=1;i<=t&&prime[i]*prime[i]<=k;i++){
		if(k%prime[i]==0)s=s/prime[i]*(prime[i]-1);
		while(k%prime[i]==0)k/=prime[i];
	}
	if(k>1)s=s/k*(k-1);
	return s;
}

int main(){
	freopen("gcdsum.in","r",stdin);freopen("gcdsum.out","w",stdout);
	scanf("%lld",&n);
    t=0;
	for(ll i=2;i*i<=n;i++){
		if(!flag[i]){
			prime[++t]=i;
			for(ll j=i+i;j*j<=n;j+=i){
				flag[j]=1;
			}
		}
	}
	for(ll i=1;i*i<=n;i++){
		if(n%i==0){
			if(i*i==n){
                ans+=ou(i)*i;
                break;
            }else{
                ans+=ou(i)*n/i+ou(n/i)*i;
            }
		}
	}
	printf("%lld\n",ans);
	return 0;
}