bzoj 3944 Sum

Description

Input

一共T+1行
第1行为数据组数T(T<=10)
第2~T+1行每行一个非负整数N，代表一组询问

Output

一共T行，每行两个用空格分隔的数ans1,ans2

Sample Input

6

1

2

8

13

30

2333

Sample Output

1 1

2 0

22 -2

58 -3

278 -3

1655470 2

题解

具体见总结

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
const int N = 5000000;
bool p[N + 10];
int n, T, pr[N + 10];
long long mu[N + 10], phi[N + 10];
map<int, long long> mpi, mmu;
void init() {
    mu[1] = phi[1] = 1;
    for (int i = 2; i <= N; ++i) {
        if (!p[i])
            pr[++pr[0]] = i, mu[i] = -1, phi[i] = 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, phi[i * pr[j]] = phi[i] * pr[j];
                break;
            }
            mu[i * pr[j]] = -mu[i], phi[i * pr[j]] = phi[i] * phi[pr[j]];
        }
    }
    for (int i = 1; i <= N; ++i) phi[i] += phi[i - 1], mu[i] += mu[i - 1];
}
long long mus(int n) {
    if (n <= N) return mu[n];
    if (mmu.count(n)) return mmu[n];
    long long tmp = 1;
    for (int i = 2, las = 0; i <= n; i = las + 1) {
        las = n / (n / i);
        tmp -= 1ll * mus(n / i) * (las - i + 1);
        if (las == n) break;
    }
    return mmu[n] = tmp;
}
long long phis(int n) {
    if (n <= N) return phi[n];
    if (mpi.count(n)) return mpi[n];
    long long tmp;
    if (n & 1) tmp = 1ll * (n + 1ll) / 2ll * 1ll * n;
    else tmp = 1ll * n / 2ll * (n + 1ll);
    for (int i = 2, las = 0; i <= n; i = las + 1) {
        las = n / (n / i);
        tmp -= 1ll * phis(n / i) * (las - i + 1);
        if (las == n) break;
    }
    return mpi[n] = tmp;
}
main() {
    init();
    scanf("%d", &T);
    while (T--)
        scanf("%d", &n), printf("%lld %lld\n", phis(n), mus(n));
}