题目大意：给定n，求出1到n所有数与n的gcd之和。 题解：我们枚举n的每一个因子d，然后计算一下1到n/d的区间内有多少个数和n/d互质，也就是欧拉函数，再将欧拉函数乘以一个d即可。
#include<cstdio>#include<cstdlib>#include<iostream>#include<iomanip>#include<ctime>#include<cmath>#include<cstring>#include<string>#include<algorithm>using namespace std;long long phi(long long x){ long long re=x; for(int i=2;i<=sqrt(x)+0.5;i++) { if(x%i==0) re-=re/i; while(x%i==0) x/=i; } if(x!=1) re-=re/x; return re;}int main(){ long long n; scanf("%lld",&n); long long ans=0; for(int i=1;i<=sqrt(n)+0.5;i++) { if(n%i==0) { ans+=i*phi(n/i); if(i!=n/i) ans+=(n/i)*phi(n/(n/i)); } } cout<<ans; return 0;}新闻热点
疑难解答
