考虑枚举gcd(i,n) =d 那么只要计数有多少个数和N的gcd是d
显然是phi(n/d)个
假设一个数可以表示成$p_{1}^{a1}+p_{2}^{a2}+...$,那么phi的结果就是 $(p_{1}-1)*p_{1}^{a1-1}*(p_{2}-1)*p_{2}^{a2-1}...$每次找到一个约数之后除干净就可以保证每次找到的都是质因数
计算phi是$\sqrt{n}$(枚举约数的复杂度) 枚举公约数$\sqrt{n}$ 时间复杂度$\sqrt{n}$
#include <cstdio> #include <algorithm> #include <cmath> using namespace std; typedef long long LL; LL n,sq,ans; LL phi(LL x){ LL tmp=(LL)sqrt(x),ret=1; for(int i=2;i<=tmp;i++){ if(x%i==0){ ret*=i-1;x/=i; while(x%i==0) x/=i,ret*=i; } } if(x>1)ret=ret*(x-1); return ret; } int main(){ scanf("%lld",&n);sq=(LL)sqrt(n); for(int i=1;i<=sq;i++){ if(n%i==0) { ans+=i*phi(n/i); if(n/i!=i) ans+=(n/i*phi(i)); } } printf("%lld",ans); }