bzoj 1968 [Ahoi2005]COMMON 约数研究
Description
Input
只有一行一个整数 N(0 < N < 1000000)。
Output
只有一行输出,为整数M,即f(1)到f(N)的累加和。
Sample Input
3
Sample Output
5
题解
具体见总结
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 37 38 39 40 41 42 |
#include <cstdio> #include <algorithm> #include <cstring> #include <map> using namespace std; const int N = 1000000; bool p[N + 10]; int n, T, pr[N + 10]; long long mu[N + 10]; map<int, long long> d; void init() { mu[1] = 1; for (int i = 2; i <= N; ++i) { if (!p[i]) pr[++pr[0]] = i, mu[i] = -1; for (int j = 1; j <= pr[0] && i * pr[j] <= N; ++j) { p[i * pr[j]] = 1; if (i % pr[j] == 0) { mu[i * pr[j]] = 0; break; } mu[i * pr[j]] = -mu[i]; } } for (int i = 1; i <= N; ++i) mu[i] += mu[i - 1]; } long long ds(int n) { if (d.count(n)) return d[n]; long long tmp = n; for (int i = 2, las; i <= n; i = las + 1) { las = n / (n / i); tmp -= 1ll * (mu[las] - mu[i - 1]) * ds(n / i); if (las == n) break; } return d[n] = tmp; } main() { init(); scanf("%d", &n); printf("%lld\n", ds(n)); } |