bzoj 1968 [Ahoi2005]COMMON 约数研究

Description

Input

只有一行一个整数 N（0 < N < 1000000）。

Output

只有一行输出，为整数M，即f(1)到f(N)的累加和。

Sample Input

3

Sample Output

5

题解

具体见总结

#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));
}