杜教筛

###前置知识

####积性函数

若函数 $f(n)$ 满足当 $gcd(i,j)=1$ 时, $f(ij)=f(i)f(j)$,那么这个函数为积性函数

常见的积性函数有

1.$\mu(n)$ —莫比乌斯函数

2.$\phi(n)$ —欧拉函数

3.$d(n)$ —约数个数

4.$\sigma(n)$ —约数和函数

####完全积性函数

待会儿会用到

1.$\epsilon(n)$ —元函数,满足 $\epsilon(n)=[n=1]$

2.$I(n)$ —恒等函数,恒等于1

3.$id(n)$ —单位函数,$id(n)=n$

可能这时你会觉得没用,当时我也是这么觉得的,但是看完下面就不会这么觉得的

####迪利克雷卷积(*)

定义:两个数论函数 $f,g$ 的卷积为 $(f*g)(n)=\sum\limits_{d|n}f(d)\times g(\frac{n}{d})$,括号表示范围

显然,满足 $f*g=g*f,(f*g)*h=f*(g*h),(f+g)*h=f*h+g*h$,即交换律,结合律,分配律

有了这个有什么用呢

之前证明过莫比乌斯反演,其实迪利克雷卷积也可以证明

证明

我们知道,莫比乌斯函数满足 $\sum\limits_{d|n}\mu(d)=[n=1]$

写成迪利克雷卷积的形式就是 $\mu*I=\epsilon$

$$F(n)=\sum\limits_{i|d}f(i)\Rightarrow F=f*I \Rightarrow F*\mu=f*I*\mu=f*\epsilon=f$$

即 $F*\mu=f$,代入后可得 $f(n)=\sum\limits_{i|d}\mu(\frac{d}{i})F(d)$

证毕

同时,它还可以用来推欧拉函数与莫比乌斯函数的关系

可以知道欧拉函数有一个性质 $\sum\limits_{d|n}\mu(d)=n$

写成迪利克雷卷积的形式就是 $\phi*I=id$

$$\Rightarrow \phi*I*\mu=id*\mu\\\Rightarrow \phi*\epsilon=id*\mu$$

即 $\phi=id*\mu\Rightarrow \phi(n)=\sum\limits_{d|n}id(\frac{n}{d})\mu(d)=\sum\limits_{d|n}\frac{n\mu(d)}{d}$

###杜教筛

说完上面那些,就可以开始讲杜教筛了

首先,杜教筛是以低于线性时间复杂度来求积性函数前缀和的筛法

即我们需要求的式子是 $\sum\limits_{i=1}^nf(i)$

为了求这个东西,我们首先构造两个积性函数,使得 $f*g=h$

不妨令 $S(n)=\sum\limits_{i=1}^nf(i)$

$$f*g=h\Rightarrow\sum\limits_{i=1}^nh(i)=\sum\limits_{i=1}^n\sum\limits_{d|i}g(d)*f(\frac{d}{i})\\=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)$$

即 $\sum\limits_{i=1}^nh(i)=\sum\limits_{d=1}^ng(d)S(\lfloor\frac{n}{d}\rfloor)$

提出第一项得到 $g(1)S(n)=\sum\limits_{i=1}^nh(i)-\sum\limits_{d=2}^ng(d)S(\lfloor\frac{n}{d}\rfloor)$

简而言之,就是用简单的去求复杂的,需要你定义的 $h,g$ 比较好求

###应用

####求 $S(n)=\sum\limits_{i=1}^n\mu(i)$

根据上述式子 $g(1)S(n)=\sum\limits_{i=1}^nh(i)-\sum\limits_{d=2}^ng(d)S(\lfloor\frac{n}{d}\rfloor)$,我们只需要找到一个 $g$使得这个式子容易求

显然 $\mu*I=\epsilon$,不妨假设 $f=\mu,g=I,h=\epsilon$

$$\Rightarrow S(n)=1-\sum\limits_{d=2}^nS(\lfloor\frac{n}{d}\rfloor)$$

这样就可已通过杜教筛求莫比乌斯函数前缀和

####求 $S(n)=\sum\limits_{i=1}^n\phi(i)$

同上,可以找到 $\phi*I=id$,假设 $f=\phi,g=I,h=id$

$$\Rightarrow S(n)=\sum\limits_{i=1}^ni-\sum\limits_{d=2}^nS(\lfloor\frac{n}{d}\rfloor)$$

####求 $S(n)=\sum\limits_{i=1}^ni\phi(i)$

相比之前的两个,这个无法直接看出需要配什么积性函数

考虑 $h(n)=\sum\limits_{d|n}(d\times\phi(d))\times g(\frac{n}{d})$

想要把其中的 $d$ 给约掉,可以尝试令 $g=id$

$$\Rightarrow\sum\limits_{d|n}(d\times\phi(d))\times \frac{n}{d}=\sum\limits_{d|n}\phi(d)\times n=n\sum\limits_{d|n}\phi(d)=n^2$$

似乎可以

代回上面的式子

$$S(n)=\sum\limits_{i=1}^ni^2-\sum\limits_{d=2}^ndS(\lfloor\frac{n}{d}\rfloor)$$

这样就可以通过整除分块快速求出了

###杜教筛的实现

先有线性筛求出一个大概的范围,然后剩下的递归处理,

【模板】杜教筛（Sum）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int M = 6e6 + 5;

bool st[M];
int prime[M], tot, mu[M], sum1[M];
ll sum2[M], phi[M];
unordered_map<ll, ll> Phi;
unordered_map<int, int> Mu;

void init()
{
    phi[1] = mu[1] = 1; 
    for (int i = 2; i < M; i++)
    {
        if (!st[i])
            prime[++tot] = i, mu[i] = -1, phi[i] = i - 1;
        for (int j = 1; i * prime[j] < M; j++)
        {
            st[i * prime[j]] = true;
            if (i % prime[j] == 0)
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            mu[i * prime[j]] = -mu[i], phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
    for (int i = 1; i < M; i++)
        sum1[i] = sum1[i - 1] + mu[i], sum2[i] = sum2[i - 1] + phi[i];
}

ll Djphi(ll x)
{
    if (x < M)
        return sum2[x];
    if (Phi[x])
        return Phi[x];
    ll res = (ll)x * (x + 1) / 2;
    for (ll l = 2, r; l <= x; l = r + 1)
    {
        r = min(x, x / (x / l));
        res -= (ll)(r - l + 1) * Djphi(x / l);
    }
    return Phi[x] = res;
}

int Djmu(ll x)
{
    if (x < M)
        return sum1[x];
    if (Mu[x])
        return Mu[x];
    int res = 1;
    for (ll l = 2, r;l <= x; l = r + 1)
    {
        r = min(x, (x / (x / l)));
        res -= (ll)(r - l + 1) * Djmu(x / l);
    }
    return Mu[x] = res;
}

int main()
{
    init();
    int T;
    scanf("%d", &T);
    while (T--)
    {
        ll n;
        scanf("%lld", &n);  
        printf("%lld %d\n", Djphi(n), Djmu(n));
    }
    return 0;
}