c/c++语言开发共享BZOJ2705: [SDOI2012]Longge的问题(欧拉函数)

题意

题目链接

sol

开始用反演推发现不会求(mu(k))慌的一批

退了两步发现只要求个欧拉函数就行了

(ans = sum_{d | n} d phi(frac{n}{d}))

理论上来说复杂度是(o(n))的，但是(d)的值十分有限。在(2^{32})内最多的约数也只有1920个。

/*  */ #include<bits/stdc++.h> #define ll long long  #define int long long  const int maxn = 1e5 + 10, inf = 1e9 + 7; using namespace std; inline int read() {     char c = getchar(); int x = 0, f = 1;     while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();     return x * f; } int n; int calc(int n) {     int res = 1;     for(int i = 2; i * i <= n; i++) {         if(n % i == 0) {             int now = (i - 1); n /= i;             while(n % i == 0) now *= i, n /= i;             res *= now;         }     }     if(n != 1) res *= (n - 1);     return res; } signed main() {     n = read();     int ans = 0;     for(int i = 1; i * i <= n; i++) {         if(n % i == 0) {             ans += i * calc(n / i);             if(i != n / i) ans += (n / i) * calc(i);         }     }     cout << ans;     return 0; } /* 3 7 a*b aebr*ob */