BZOJ3944 Sum <杜教筛>

Problem

Sum

Description

Input

一共行
第行为数据组数
第行每行一个非负整数，代表一组询问

Output

一共行，每行两个用空格分隔的数

Sample Input

Sample Output

标签：杜教筛

Solution

杜教筛板题。

首先推杜教筛通式。
对于积性函数，若，即，那么可以得到

这样就可以预处理较小的后数论分块求解。

然后对于题目中的两问分别推式子：

注意将两个答案的求解放在一起，用pair<long,long>返回，否则可能。

Code

#include <bits/stdc++.h>
#define MX 2500000
#define fir first
#define sec second
#define mp make_pair
#define pll pair<lnt,lnt>
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int cnt, pri[MX+5]; lnt phi[MX+5], mu[MX+5];
bool NotPri[MX+5]; map <lnt, lnt> ex1, ex2;
void init() {
    phi[1] = mu[1] = 1;
    for (int i = 2; i <= MX; i++) {
        if (!NotPri[i]) pri[cnt++] = i, phi[i] = i-1, mu[i] = -1;
        for (int j = 0; j < cnt; j++) {
            if (i*pri[j] > MX) break;
            NotPri[i*pri[j]] = true;
            if (i%pri[j]) phi[i*pri[j]] = phi[i]*(pri[j]-1), mu[i*pri[j]] = -mu[i];
            else {phi[i*pri[j]] = phi[i]*pri[j], mu[i*pri[j]] = 0; break;}
        }
        phi[i] += phi[i-1], mu[i] += mu[i-1];
    }
}
pll sum(lnt n) {
    if (n <= MX) return mp(phi[n], mu[n]);
    if (ex1[n]) return mp(ex1[n], ex2[n]);
    lnt ret1 = 1LL*n*(n+1)/2, ret2 = 1LL; pll t;
    for (lnt l = 2, r; l <= n; l = r+1)
        r = n/(n/l), t = sum(n/l), 
        ret1 -= 1LL*(r-l+1)*t.fir, 
        ret2 -= 1LL*(r-l+1)*t.sec;
    return mp(ex1[n] = ret1, ex2[n] = ret2);
}
void sol(lnt n) {
    pll ans = sum(n);
    printf("%lld %lld\n", ans.fir, ans.sec);
}
int main() {
    lnt T, n;	read(T), init();
    while (T--) read(n), sol(n);
    return 0;
}