題目大意：給定n，求出1到n所有數(shù)與n的gcd之和。 題解：我們枚舉n的每一個因子d，然后計算一下1到n/d的區(qū)間內(nèi)有多少個數(shù)和n/d互質(zhì)，也就是歐拉函數(shù)，再將歐拉函數(shù)乘以一個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;}新聞熱點
疑難解答
