[BZOJ 4805] 欧拉函数求和

题目大意

给定 $n$，求

$\sum_{i = 1}^{n} \varphi(i)$

$1 \leqslant n \leqslant 2,000,000,000$

题目链接

BZOJ 4805

题解

杜教筛模版题。

狄利克雷卷积有 $\varphi \times 1 = id$，则有：

$\Phi(n) = \frac{n (n + 1)}{2} - \sum_{i = 2}^{n} \Phi(\lfloor \frac{n}{i} \rfloor)$

预处理出前 $n^{\frac{2}{3}}$ 项，复杂度为 $O(n^{\frac{2}{3}})$。

代码

把 < MAXNN 写成了 <= MAXNN，RE了四次。。。

#include <cstdio>
#include <map>
const int MAXNN = 1600000;
long long phi[MAXNN];
int prime[MAXNN], primeCnt;
bool notPrime[MAXNN];
void linearShaker() {
    phi[1] = 1;
    notPrime[0] = notPrime[1] = true;
    for (int i = 2; i < MAXNN; i++) {
        if (!notPrime[i]) {
            prime[++primeCnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= primeCnt && i * prime[j] < MAXNN; j++) {
            notPrime[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
    for (int i = 2; i < MAXNN; i++) phi[i] += phi[i - 1];
}
long long pSumPhi(int n) {
    if (n < MAXNN) return ::phi[n];
    static std::map<int, long long> phi;
    std::map<int, long long>::iterator it;
    if ((it = phi.find(n)) != phi.end()) return it->second;
    long long res = (long long) n * (n + 1) / 2;
    int last;
    for (int i = 2; i <= n; i = last + 1) {
        last = n / (n / i);
        res -= (last - i + 1) * pSumPhi(n / i);
    }
    return phi[n] = res;
}
int main() {
    int n;
    scanf("%d", &n);
    linearShaker();
    printf("%lld\n", pSumPhi(n));
    return 0;
}