一堆数学的玩意和补充：欧拉函数、狄利克雷卷积、杜教筛

上次讲了莫比乌斯函数和莫比乌斯反演，这次就来补充一下之前没讲到的东西吧。

欧拉函数

定义一个数的欧拉函数为小于并且与的最大公约数为（即互质）的数的个数。

例如：，因为均与互质。

我们在这里探讨一下欧拉函数的性质：

如果是质数，那么很明显的、。
欧拉函数是积性函数，所以当两个数互质时，。
。考虑如何证明。

假设这里设。先把所有以为分母，分子小于等于的分数列出来。
$\frac{1}{12},\frac{2}{12},\frac{3}{12},\frac{4}{12},\frac{5}{12},\frac{6}{12},\frac{7}{12},\frac{8}{12},\frac{9}{12},\frac{10}{12},\frac{11}{12},\frac{12}{12}$
然后约分：
$\frac{1}{12},\frac{1}{6},\frac{1}{4},\frac{1}{3},\frac{5}{12},\frac{1}{2},\frac{7}{12},\frac{2}{3},\frac{3}{4},\frac{5}{6},\frac{11}{12},\frac{1}{1}$
会发现这里的所有分子和分母都是互质的。而这里的分母全部都是的因数，并且这些因数的所有和这些因数互质的数都做了这些因数的分子。就拿举例，与互质的所有数都在已为分母的分子上，一共个互质的数。

所以可以发现，。

由特殊到一般，对于的每一个因数，和与互质并的数，和组成的分数和原来以为分母的分数是一一对应的。即可证明。
若且为质数，那么只有个数与其不互质，那么。
因为每一个数可以被分解为一堆质数的和，设（其中为质数），那么因为和一定是互质的，所以。

根据最后一个定理，我们就可以使用线性筛求的所有欧拉函数了。

int phi[N], prime[N], primecnt;
bool vis[N];
int n;
inline void init(){
    vis[1] = phi[1] = 1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            prime[++primecnt] = i;
            phi[i] = i-1;
        }
        for(int j=1;prime[j]*i<=n&&j<=primecnt;j++){
            vis[i*prime[j]] = 1;
            phi[i*prime[j]] = (i%prime[j]? phi[i]*(prime[j]-1): phi[i]*prime[j]);
            if(i%prime[j] == 0) break;
        }
    }
}

根据这个定理：

$\sum_{d\mid n} \varphi(d) = n$

可以解决一系列的问题。这种思想和莫比乌斯反演非常相似，这里暂且先把它叫做欧拉反演。

欧拉反演

还是以举例子：

$\begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{n} \gcd(i, j)\\ = &\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{d\mid i \land d \mid j}\varphi(d) \\ = & \sum_{d\mid i \land d \mid j} \varphi(d)\sum_{i=1}^{n}\sum_{j=1}^{n} 1\\ = & \sum_{d=1}\varphi(d) \lfloor\frac{n}{d}\rfloor^2 \end{aligned}$

然后，处理前缀和，整除分块，步骤和莫比乌斯反演一样。

欧拉定理

若，则。

这个定理经常用于大家都熟悉的费马小定理快速幂求逆元。

狄利克雷卷积

对于两个数论函数（定义域为正整数、值域为复数的函数）和，定义两个函数的狄利克雷卷积 $(fg)(x) $为（此处令$ h(x) = (fg)(x)$）：

$(f*g)(x) = \sum_{d\mid x}f(d)g(\frac{x}{d}) = \sum_{d\mid x}f(\frac{x}{d})g(d)$

狄利克雷卷积运算满足交换律、结合律和分配律。

而狄利克雷卷积中有三个特殊的函数：

元函数：
常数函数：
恒等函数：

这里列举一些常考的一些函数的卷积关系：

$\mu 1 = \varepsilon $。因为根据莫比乌斯反演：$ \displaystyle \sum_{d\mid n} \mu(d) = [n=1] $，$ \mu 1 = \displaystyle\sum_{d\mid x}\mu(d)1(\frac{x}{d}) = \sum_{d\mid x} \mu(d) = [x=1] = \varepsilon$
。根据欧拉反演：，类似上面的证明即得证。
$\mu id = \varphi $。我们可以根据关系把$ id $拆为$ \varphi 1 $，于是原式就变为$ \mu\varphi1 = \mu1\varphi = \varepsilon * \varphi = \varphi$。

注意：定理 3 是莫比乌斯函数和欧拉函数的关系，一定要理解、记住、背过！

根据上面的卷积关系，我们引入一个复杂度为求（为积性函数）的一种新算法：杜教筛。

杜教筛

这里令。我们要求的就是。

之前我们学了狄利克雷卷积，而杜教筛就是利用了卷积，先构造积性函数，使能够在非常小的时间复杂度内算出来，然后利用下列递推式递归求出：

$g(1)s(n) = \sum_{i=1}^{n} (f * g)(i) - \sum_{i=2}^{n} g(i)s(\lfloor\frac{n}{i}\rfloor)$

考虑这个递推式如何证明：

$\begin{aligned} &\sum_{i=1}^{n} (f*g)(i) \\ = &\sum_{i=1}^{n}\sum_{d\mid i} f(\frac{i}{d})g(d) \\ = &\sum_{i=1}^{n}\sum_{d=1}^{n} [d\mid i] f(\frac{i}{d}) g(d) \\ = &\sum_{d=1}^{n}\sum_{i=1}^{n} [d\mid i] f(\frac{i}{d}) g(d) \\ = &\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)g(d) \\ = &\sum_{d=1}^{n}g(d)s(\lfloor\frac{n}{d}\rfloor) \\ = &g(1)s(n) + \sum_{d=2}^{n} g(d)s(\lfloor\frac{n}{d}\rfloor) \end{aligned}$

于是，我们就可以根据之前的值得出。

在做杜教筛时要有几个小技巧：

首先预处理（这里的一般较小，在左右），只要的，就直接返回预处理的值。
用一个 map 来存储已经算过的，记忆化搜索，使其不会重复计算。
因为其中带了一个，所以可以用整除分块做。

现在以一道例题来讲一下杜教筛的应用。

O(n^2/3) 求莫比乌斯函数和欧拉函数前 n 项的和

现在要求，那就要构造一个函数使得是非常好求的。

回想一下之前的一些常考的卷积关系，里面有一项：，于是就可以令，然后带入杜教筛的式子得：

$\begin{aligned} 1 \times s(n) &= \sum_{i=1}^{n} \varepsilon(i) - \sum_{i=2}^{n} 1\times s(\lfloor\frac{n}{i}\rfloor)\\ s(n) &= 1 - \sum_{i=2}^{n}s(\lfloor\frac{n}{i}\rfloor) \end{aligned}$

于是就可以预处理 + map 记忆化 + 整除分块来递归求这种数据规模的值了。

const int L = 2e6;
void init(){
    ...
}
unordered_map<int, int> mob_map;
int getsummob(ll x){
    if(x <= L) return summob[x];
    if(mob_map.count(x)) return mob_map[x];
    ll ans = 1;
    for(ll l=2,r;l<=x;l=r+1){
        r = (x/(x/l));
        ans -= (r-l+1)*getsummob(x/l);
    }
    mob_map[x] = ans;
    return ans;
}

求欧拉函数前缀和也类似，设，根据，带入杜教筛式子可得：

$\begin{aligned} s(n) = (1 + 2 + \cdots + n) - \sum_{i=2}^{n} s(\lfloor \frac{n}{i}\rfloor) \end{aligned}$

前面那个等差数列就用求和公式求，后面那个一样用整除分块。

unordered_map<int, ll> phi_map;
ll getsumphi(ll x){
    if(x <= L) return sumphi[x];
    if(phi_map.count(x)) return phi_map[x];
    ll ans = 1ll*(x)*(x+1)/2;
    for(ll l=2,r;l<=x;l=r+1){
        r = (x/(x/l));
        ans -= (r-l+1)*getsumphi(x/l);
    }
    phi_map[x] = ans;
    return ans;
}

其它的杜教筛求前缀和也和这个思想一样，只要构造出好求的，规模在左右，就可以用杜教筛来求一个积性函数的前缀和。