傳送門 我們可以先枚舉最小公倍數，設其為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); }新聞熱點
疑難解答
