BZOJ3944 Sum <杜教筛>

Posted on Symbols count in article: 675 Reading time ≈ 2 mins.

Problem

Sum

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

求ans1=∑i=1nϕ(i)ans_1=\sum_{i=1}^n\phi(i)和ans2=∑i=1nμ(i)ans_2=\sum_{i=1}^n\mu(i)。
n<231n<2^{31}，TT组询问。

Input

一共T+1T+1行
第11行为数据组数T(T≤10)T(T\le10)
第2∼T+12\sim T+1行每行一个非负整数NN，代表一组询问

Output

一共TT行，每行两个用空格分隔的数ans1,ans2ans_1,ans_2

Sample Input

1
2
3
4
5
6
7
6
1
2
8
13
30
2333

Sample Output

1
2
3
4
5
6
1 1
2 0
22 -2
58 -3
278 -3
1655470 2

标签：杜教筛

Solution

杜教筛板题。

首先推杜教筛通式。
对于积性函数f,g,hf,g,h，若h=f⊗gh=f\otimes g，即h(n)=∑d∣nf(d)g(nd)h(n)=\sum_{d|n}f(d)g(\frac{n}{d})，那么可以得到

∑i=1nh(i)=∑i=1n∑d∣if(d)g(nd)=∑i=1ng(i)∑d=1⌊n/i⌋f(d)=∑i=1ng(i)S(⌊ni⌋)=∑i=2ng(i)S(⌊ni⌋)+g(1)S(n)∴S(n)=∑i=1nh(i)−∑i=2ng(i)S(⌊ni⌋)g(1)\begin{aligned} \sum_{i=1}^{n}h(i)&=\sum_{i=1}^{n}\sum_{d|i}f(d)g(\frac{n}{d})\\ &=\sum_{i=1}^{n}g(i)\sum_{d=1}^{\lfloor n/i\rfloor}f(d)\\ &=\sum_{i=1}^{n}g(i)S(\lfloor\frac{n}{i}\rfloor)\\ &=\sum_{i=2}^{n}g(i)S(\lfloor\frac{n}{i}\rfloor)+g(1)S(n)\\ \therefore S(n)&=\frac{\sum_{i=1}^{n}h(i)-\sum_{i=2}^{n}g(i)S(\lfloor\frac{n}{i}\rfloor)}{g(1)} \end{aligned}

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

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

Calculate  ∑i=1nμ(i).∵∑d∣nμ(d)=[n=1]=e(n)∴e=μ⊗1⇒S(n)=1−∑i=2nS(⌊ni⌋)Calculate\;\sum_{i=1}^{n}\mu(i).\\ \begin{aligned} &\because\sum_{d|n}\mu(d)=[n=1]=e(n)\\ &\therefore e=\mu\otimes1\\ &\Rightarrow S(n)=1-\sum_{i=2}^{n}S(\lfloor\frac{n}{i}\rfloor) \end{aligned}

Calculate  ∑i=1nφ(i).∵∑d∣nφ(d)=n=id(n)∴id=φ⊗1⇒S(n)=n×(n+1)2−∑i=2nS(⌊ni⌋)Calculate\;\sum_{i=1}^{n}\varphi(i).\\ \begin{aligned} &\because\sum_{d|n}\varphi(d)=n=id(n)\\ &\therefore id=\varphi\otimes1\\ &\Rightarrow S(n)=\frac{n\times(n+1)}{2}-\sum_{i=2}^{n}S(\lfloor\frac{n}{i}\rfloor) \end{aligned}

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

Code

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
43
44
45
46
47
#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;
}