@OceanEye6年前
04/10
21:14
目测这题很水，那么多人都A了= =
确实也是比较水的。只要有些数论函数的基础就可以做了
gcd(i,N)==k的个数是phi(N/i)，所以每一个因数对sum的贡献就是i*phi(N/i)
就酱。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <cstdio> #include <algorithm> #include <cmath> #define ll long long using namespace std; ll calc_phi(ll x) { ll ret=1; for(int i=2;i*i<=x;i++) { if(x%i!=0) continue; ret*=(i-1); x/=i; while(x%i==0) { ret*=i; x/=i; } } if(x>1) ret*=(x-1); return ret; } ll N,ans,M; int j; int main() { scanf("%lld",&N); M=sqrt(N); for(int i=1;i<=M;i++) { if(N%i) continue; j=N/i; ans+=i*(calc_phi(j)); if(j!=i) ans+=j*(calc_phi(i)); } printf("%lld",ans); return 0; } |
前排到此一游