欧拉函数&莫比乌斯函数&狄利克雷卷积&杜教筛

CR380AL · 2025-05-26 17:30:14 · 算法·理论

欧拉函数

定义

定义 \varphi(n) 表示小于等于 n 的正整数中与 n 互质数的数量。

基本性质

• 性质 1：是积性函数，即对于 \forall \gcd(a,b)=1，满足 \varphi(ab)=\varphi(a)\cdot\varphi(b)。

  这个不太会证明。（我有点废物了）

• 性质 2：当 n 是奇数时。\varphi(2n)=\varphi(n)。
• 性质 3：当 p 是质数时。\varphi(p^k)=p^k-p^{k-1}。
• 性质 4：由唯一分解定理，设 n=\prod\limits_{i=1}^kp_i^{c_i}，同时根据性质 1 和性质 3 可以非常容易的推出 \varphi(n)=n\cdot \prod\limits_{i=1}^k\frac{p_i-1}{p_i}

• 性质 5：n=\sum\limits_{d|n}\varphi(d)。

  证明如下：设 \gcd(k,n)=d,(k<n)，则显然有 \gcd(\frac{k}{d},\frac{n}{d})=1。设 f_i 表示 \gcd(k,n)=x 的 k 数量。则有 n=\sum\limits_{i=1}^n f_i，显然其可以变化为 n=\sum\limits_{i=1}^n \varphi(\frac{n}{i}) ，当然也可以得到最后的式子 n=\sum\limits_{d|n}\varphi(d)。

线性筛求欧拉函数

inline void Euler(){
    phi[1]=1;
    for(int i=2;i<=5e6;i++){
        if(!is[i]){
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&prime[j]*i<=5e6;j++){
            is[prime[j]*i]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}

莫比乌斯函数

定义

性质

• 性质 1：\sum\limits_{d|n}\mu(d)=\begin{cases}1 & n=1\\ 0 & n\ne 1\end{cases},即 \sum\limits_{d|n}\mu(d)=\varepsilon 或者是 \mu * 1=\varepsilon。

  证明如下：先将 n 按唯一分解定理分解为 \prod\limits_{i=1}^k p_i^{c_i} ,发现莫比乌斯函数指数大于 1 部分没有作用所以令 n_2=\prod\limits_{i=1}^k p_i ，对 n_2 代入计算出的结果和 n 是完全等价的。\sum\limits_{d|n}\mu(d)=\sum\limits_{i=0}^k C_k^i \cdot (-1)^i=\sum\limits_{i=0}^k (1+(-1))^k。这里就证明结束了。

• 性质 2：应用性质 1 的结论得到 [\gcd(i,j)=1]=\sum\limits_{d|\gcd(i,j)}\mu(d)。
• 性质 3：\mu(ij)=[\gcd(i,j)=1]\mu(i)\mu(j)。

线性筛求莫比乌斯函数

inline void Euler(){
    mu[1]=1;
    for(int i=2;i<=2e7;i++){
        if(!is[i]){
            prime[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&prime[j]*i<=2e7;j++){
            is[i*prime[j]]=true;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
}

习题

P2522 [HAOI2011] Problem b

不难想到把这个要求的东西看做一个 (a,c)\rarr(b,d) 的矩形，直接二维前缀和一样的做差将其分为 4 个 (1,1)\rarr(n,m) 的块计算。 对于一个块其贡献推导如下：

我们用线性筛维护出来 S(i) 然后又是熟悉的根号分块。

代码展示一下 S(i) 的求法：

// d数组一开始求每个数的约数个数，最后在前缀和与S数组内涵对齐。
// num 表示一个数最小质因数出现的次数
inline void Euler(){
    d[1]=1;
    for(int i=2;i<=5e4;i++){
        if(!is[i]){
            prime[++cnt]=i;
            num[i]=1;
            d[i]=2;
        }
        for(int j=1;j<=cnt&&prime[j]*i<=5e4;j++){
            is[prime[j]*i]=true;
            d[i*prime[j]]=d[i]*2;
            num[i*prime[j]]=1;
            if(i%prime[j]==0){
                d[i*prime[j]]=d[i]/(num[i]+1)*(num[i]+2);
                num[i*prime[j]]=num[i]+1;
                break;
            }
        }
    }
    for(int i=1;i<=5e4;i++)d[i]+=d[i-1];
}

AC记录

P12599 常数要较小

钦定 S(n)=\sum\limits_{i=1}^n f(i)

如果我们要求 S(n),则可以根据这个式子列出一个方程。

如果我们能构造出适当的数论函数 g 满足以下所有条件：

1. 快速计算 \sum\limits_{i=1}^n (f*g)(i)。
2. 快速计算 g 的前缀和，并通过根号分块计算 \sum\limits_{i=2}^n g(i)\cdot S(\lfloor \frac{n}{i}\rfloor)。

则可以进行杜教筛。

杜教筛过程如下：

1. 线性筛预处理前 n^{\frac{2}{3}} 的 S(i)。
2. 递归求 S(n)，小于等于 n^{\frac{2}{3}} 部分直接调用，大于使用map记忆化并使用根号分块按上面的式子计算。

时空复杂度

作者不会积分，所以暂时不会证明。 贴一个证明：oi.wiki 。

空间复杂度：O(n^{\frac{2}{3}})。

时间复杂度：O(n^{\frac{2}{3}})。

习题

P4213 【模板】杜教筛

对于欧拉函数，将其按照上面的式子展开为：

欧拉函数的性质5 非常牛x,观察等式右端的狄利克雷卷积，直接令 g=1 ，\sum\limits_{i=1}^n (\varphi*g)(i)=\sum\limits_{i=1}^n\sum\limits_{d|i}\varphi(i)g(\frac{i}{d})=\sum\limits_{i=1}^n i=\frac{n(n+1)}{2}。

对于莫比乌斯函数，将其按照上面的式子展开为：

莫比乌斯函数的性质1 非常牛x，观察等式右端的狄利克雷卷积，直接也令 g=1，\sum\limits_{i=1}^n (\mu*g)(i)=\sum\limits_{i=1}^n\sum\limits_{d|i}\mu(i)g(\frac{i}{d})=\sum\limits_{i=1}^n\sum\limits_{d|i}\mu(i)=\sum\limits_{i=1}^n[i=1]=1。

直接开写，放一份代码。

//Syt forever!
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxn=2e7+10;
int T,n,cnt;
int mu[maxn],phi[maxn],prime[maxn];
bool is[maxn];
map<int,int>umu,uphi;
inline void Euler(){
    mu[1]=1;
    phi[1]=1;
    for(int i=2;i<=2e7;i++){
        if(!is[i]){
            prime[++cnt]=i;
            phi[i]=i-1;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&prime[j]*i<=2e7;j++){
            is[i*prime[j]]=true;
            if(i%prime[j]==0){
                mu[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<=2e7;i++){
        mu[i]+=mu[i-1];
        phi[i]+=phi[i-1];
    }
}
inline pair<int,int> get(int x){
    if(x<=2e7)return make_pair(phi[x],mu[x]);
    if(uphi[x])return make_pair(uphi[x],umu[x]);
    int ans_phi=x*(x+1)/2,ans_mu=1;
    for(int i=2,j;i<=x;i=j+1){
        j=n/(n/i);
        pair<int,int>p;
        p=get(x/j);
        ans_phi-=(j-i+1)*p.first;
        ans_mu-=(j-i+1)*p.second;
    }
    uphi[x]=ans_phi;
    umu[x]=ans_mu;
    return make_pair(ans_phi,ans_mu);
}
signed main(){
    Euler();
    scanf("%lld",&T);
    while(T--){
        scanf("%lld",&n);
        pair<int,int>p;
        p=get(n);
        printf("%lld %lld\n",p.first,p.second);
    }
    return 0;
}

这道题比较恶心的是杜教筛 10 次,map调用量过多，代码常数非常大，线性筛多预处理一些前缀和。

AC记录

P3768 简单的数学题

前置知识：\sum\limits_{i=1}^n i=\frac{n(n+1)}{2}，\sum\limits_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6},\sum\limits_{i=1}^n i^3=(\sum\limits_{i=1}^n i)^2=\frac{n^2(n+1)^2}{4}。

开始推式子。

到这里发现这个式子后面的 (\sum\limits_{i=1}^{\lfloor \frac{n}{k}\rfloor}i)^2 能根号分块计算，现在的问题就是求 S(n)=\sum\limits_{k=1}^n \varphi(k)\cdot k^2 。将其按照杜教筛狄利克雷卷积形式展开如下：

将 \sum\limits_{i=1}^n (f*g)(i) 展开为 \sum\limits_{i=1}^n \sum\limits_{d|i}\varphi(d)\cdot d^2 \cdot g(\frac{i}{d})

仿照模板题的方式，尝试让 g(i)=i^2 ，则会惊人的发现 \sum\limits_{i=1}^n (f*g)(i)=\sum\limits_{i=1}^n i^3。而 \sum\limits_{i=2}^n g(i)\cdot S(\lfloor \frac{n}{i}\rfloor) 也可以用前置知识＋根号分块快速计算。

因为这道题是根号分块上分的部分求前缀和，所以其再调用根号分块会使用到之前的部分。直观感觉多次杜教筛和一次杜教筛没有区别，时间复杂度依然正确。

AC记录