题意
题目链接
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 */
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605260.html