传送门 我们可以先枚举最小公倍数，设其为x，时间O（sqrt(n)) 然后可以求出与n/x互质的数，时间O（sqrt(n/x)) 时间复杂度远跑不到O（n)上界
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#define ll long longll n,ans;ll euler(ll x){ ll s=x; for (int i=2;i*i<=x;i++) if (x%i==0){ s=s/i*(i-1); while (x%i==0) x/=i; } if (x!=1) s=s/x*(x-1); return s;}int main(){ scanf("%lld",&n); for (ll i=1;i*i<=n;i++) if (n%i==0){ ans+=i*euler(n/i); if (i*i<n) ans+=(n/i)*euler(i); } PRintf("%lld",ans);}新闻热点
疑难解答
