bzoj2705: [SDOI2012]Longge的问题

2017-3-8来源:ASP.NET技巧人气:278

传送门 我们可以先枚举最小公倍数,设其为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 long ll 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); }