Firsry AC/WA/RE/TLE
  2025-08-24 17:31 2025-08-24 17:31 Created   2025-08-24 17:31 2025-08-24 17:31 Updated

前置知识：整除分块

LaTeX 数学公式大全

配套题单

数论函数

艾佛森括号

此处 是一个可真可假的命题。

这里 的含义为：若 为真则为 ，否则为 。

数论函数

定义域为正整数（或整数），而函数值在复数域中取值的函数称为 数论函数。

积性函数

设 为数论函数且当 时，有 ，则称 为积性函数。

容易看出，对于任何积性函数有 。

特别的，若数论函数 对于任何 都有 ，则称 为完全积性函数。

常见的函数

  • 单位函数 的定义为 。

显然，单位函数是积性函数，也是完全积性函数。

  • 除数函数 表示 的因子的 次方之和。

形式化的， 。

的约数个数 常记为 ，约数和 常记为 。

除数函数是积性函数。

  • 幂函数 ， 。

一般的， 表示取值恒为 的常函数。

幂函数是完全积性函数。

欧拉函数

定义

表示在 中与 互质的数。

形式化的，

是积性函数，但不是完全积性函数。

计算

通过容斥原理可以得到：

其中 是 的标准分解。

时间复杂度 ，代码略。

  • 若 且 ，
  • 若 且 ，

对于第一点，我们会发现 和 分解质因数后 所有的质因子相同，只是指数不同。

那么我们可以将其按照欧拉函数的计算式展开，并相除，可得：

对于第二点，我们会发现 与 互质。

事实上，仍然可以用上面的展开计算，但是还可以利用积性函数的性质，得到：$\varphi(n)=\varphi(\dfrac{n}{p})\varphi(p)=\varphi(\dfrac{n}{p})(p-1)$。

就可以利用 欧拉筛 在 的时间内计算 在 到 处的取值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
memset(prime,true,sizeof(prime));
prime[0]=prime[1]=false;
sum[1]=phi[1]=1;

for (int i=2;i<=MAXN;i++){
    if (prime[i]){
        primes[++tot]=i;
        phi[i]=i-1;
    }

    for (int j=1;j<=tot&&primes[j]*i<=MAXN;j++){
        prime[i*primes[j]]=false;
        if (i%primes[j]==0){
            phi[i*primes[j]]=phi[i]*primes[j];
            break;
        }
        else phi[i*primes[j]]=phi[i]*(primes[j]-1);
    }
}

习题

欧拉反演

事实上，这东西应用范围还挺小的，但是有时候的确好用。

证明

这个性质的证明需要我们从 到 中的所有整数按照与 的 来分类，就是 ，其中每次内层计算的就是 的数的个数，枚举所有 总个数就是 了。

若 ，那么 。

此处的 相当于上一个式子的 。

根据欧拉函数的定义式，。

我们考虑所有的 时，也就同时考虑到了所有 到 之间的所有 ，所以就有了下面这个式子：

证毕。

应用

主要是应用于 求和形式的式子，直接把 换成 即可。

例题：

不妨先令 。

然后就可以整除分块了，这推式子速度比莫比乌斯快了不知道多少。

习题

莫比乌斯函数

定义

莫比乌斯函数 的定义为

其中 为不同的质数

容易看出， 在 无平方因子时非 。

是 积性函数。

计算

通过定义可以和欧拉函数一起筛。

线性筛：

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
typedef long long ll;
ll phi[N],mu[N],prime[N];
ll sumphi[N],summu[N];
bool isprime[N];
int n,cnt;
void init(){
    phi[1]=mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!isprime[i]){
            prime[++cnt]=i;
            phi[i]=i-1,mu[i]=-1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
            isprime[i*prime[j]]=1;
            if(!(i%prime[j])){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
            mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<=n;i++){
        sumphi[i]=sumphi[i-1]+phi[i];
        summu[i]=summu[i-1]+mu[i];
    }
}

狄利克雷卷积

定义

设 是数论函数，且数论函数 满足：

则称 为 的 Dirichlet 卷积， 记作 。

性质

对于任意数论函数 ，有 ，即单位函数 是 Dirichlet 卷积的 单位元。

Dirichlet 卷积满足 交换律和结合律。

若 为积性函数，则 也是积性函数。

应用

约数个数函数：。

除数函数：。

欧拉函数的性质可以写成：。

莫比乌斯函数的性质有：。

即： 。

证明

设 有 个不同的质因子，由于 当且仅当 无平方因子，故 中每个素因子的指数只能为 或 。

相当于在 个不同的质因子中选 个的贡献，选了 个贡献就是 （后面的括号就是不计排列顺序 个物品选 个的方案数）。

后面的等号就是二项式定理，小学奥数肯定讲过的啊。

然后就发现右边那个东西就是 。

证毕。

应用

例题：

这个性质很常用，应熟记于心。

习题

莫比乌斯变换

我们有数论函数 ，定义数论函数 。

若 ，

则称 为 的 Mobius 变换 ， 为 的 Mobius 逆变换。

写成 Dirichlet 卷积 的形式即为 。

莫比乌斯反演

莫比乌斯反演定理指出，上式的充要条件为：

写成 Dirichlet 卷积 形式即为 。

证明

科技

约数个数函数

性质1

然后就可以整除分块。就是这题。

性质2

事实上这个函数也是可以线性筛的。

积性函数不都可以。

但需要一个辅助数组记录当前质数的指数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
d[1]=1;
for(int i=2;i<=n;i++){
    if(!isprime[i]){
        prime[++cnt]=i;
        num[i]=1;
        d[i]=2;
    }
    for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
        isprime[i*prime[j]]=1;
        if(!(i%prime[j])) {
            num[i*prime[j]]=num[i]+1;
            d[i*prime[j]]=d[i]/num[i*prime[j]]*(num[i*prime[j]]+1);
            break;
        }
        num[i*prime[j]]=1;
        d[i*prime[j]]=d[i]<<1;
    }
}

性质3

神奇科技。

把每个质因子分开来考虑。

假设 有 个质因子 ， 有 个质因子 。

那么左边这一个质数的贡献就是 （指数加一连乘积小奥回忆）。

右边，假设每次从 中取 个因子 ，从 中取 个因子 ：

  • ，有 种情况。
  • ，有 种情况。
  • ，有 种情况。

总共也还是 种情况。

Dirichlet 前缀和

P5495 Dirichlet 前缀和

给定一个长度为 的数列 。

现在你要求出一个长度为 的数列 ，满足

首先， 有一个直接暴力枚举每个数的方法：

1
2
3
for(int i=1;i<=n;i++)
    for(int j=1;i*j<=n;j++)
        b[i*j]+=a[i];

时间复杂度为 ，显然这题不可能让你就这么过了的。

事实上，在计算的时候，我们可以借助之前计算出的结果帮助计算。

我们发现，对于每个 ，它可以由 转移过来，其中 是 的质因子。也就是说，只需要对于每个 ，枚举 的质数倍，用 更新 就可以了，正确性证明和埃氏筛类似。

时间复杂度为 。

1
2
3
for(int i=1;i<=cnt;i++)
     for(int j=1;prime[i]*j<=n;j++)
         a[prime[i]*j]+=a[j];

Dirichlet 后缀和

题面改为 ，其他不变。

下标从 转移到 ，倒序遍历即可。

1
2
3
for(int i=1;i<=cnt;i++)
    for(int j=n/prime[i];j;j--)
        a[j]+=a[prime[i]*j];

杜教筛

  • 求 ，其中 为积性函数。
  • 。

算法

显然，线性筛是 的，过不了。

考虑推数学式子。

构造积性函数 ，使得 。

有：

因为我们要算的是 ，那把这项单独拎出来:

所以有：

于是我们只要能快速算出 的前缀和就可以了。

P4213 【模板】杜教筛（Sum）

筛 ：

构造 ，

可得 。

筛 ：

构造 ，

可得 。

时间复杂度

上面的口胡代码的复杂度是 。

还可以进一步优化杜教筛，即先线性筛出前 个答案，之后再用杜教筛。当 时，复杂度为 。

可以使用哈希表来存下已经求过的答案进行记忆化。

考虑到上面的求和过程中出现的都是 。开一个大小为两倍 的数组 记录答案。如果现在需要求出 GetSum(x) ，若 ，返回 f[x] ，否则返回 f[sqrt(n)+n/i] 即可。这样可以省去哈希表的复杂度。

但实际上我这么写跑得更慢以至于过不去。。。

【代码】

常用式子总结

一些好用（？）的式子。

参考

莫比乌斯反演与数论函数

浅谈莫反

数论函数

数论公式总结

铃悬的数学小讲堂——狄利克雷卷积与莫比乌斯反演

  • Title:
  • Author: Firsry
  • Created at : 2025-08-24 17:00:31
  • Updated at : 2025-08-24 17:00:31
  • Link: https://firsryfan.github.io/2025/08/24/数论函数小结/
  • License: This work is licensed under CC BY-NC-SA 4.0.
On this page
  1. 前置知识：整除分块
  • LaTeX 数学公式大全
    1. 配套题单
  • 数论函数
    1. 艾佛森括号
    2. 数论函数
    3. 积性函数
    4. 常见的函数
  • 欧拉函数
    1. 定义
    2. 计算
      1. 习题
    3. 欧拉反演
      1. 证明
      2. 应用
      3. 习题
  • 莫比乌斯函数
    1. 定义
    2. 计算
  • 狄利克雷卷积
    1. 定义
    2. 性质
    3. 应用
      1. 证明
      2. 应用
      3. 习题
    4. 莫比乌斯变换
    5. 莫比乌斯反演
      1. 证明
  • 科技
    1. 约数个数函数
      1. 性质1
      2. 性质2
      3. 性质3
    2. Dirichlet 前缀和
      1. P5495 Dirichlet 前缀和
    3. Dirichlet 后缀和
  • 杜教筛
    1. 算法
    2. P4213 【模板】杜教筛（Sum）
    3. 时间复杂度
  • 常用式子总结
  • 参考