当前位置：首页 > news >正文

【数论】莫比乌斯函数及其反演

news 来源：原创 2025/8/3 7:07:31

文章目录

一、介绍
二、莫比乌斯函数的算法求解
三、例题

在学习之前，先来了解一下常见定义吧（OVO）：

常见数论函数分为两种：
$\begin{cases} &完全积性函数：对于任意p,q \in N，有f(p \cdot q) = f(p) \cdot f(q)\\ &积性函数：对于任意p,q \in N且gcd(p,q) = 1，有f(p \cdot q) = f(p) \cdot f(q)\\ &非积性函数 \end{cases}$
常见的完全积性函数有：单位函数 $\epsilon(n) = [n == 1]$ ，常数函数 $I (n) == 1$ ，恒等函数 $I d (n) == n$ 等；
常见的积性函数有：莫比乌斯函数 $\mu(n)$ ，欧拉函数 $\psi(n)$ ，约数和函数 $\sigma(n) = \sum_{d | n} d$ 等。
狄利克雷卷积定义：若 $f (n), g (n)$ 均为数论函数，则 $\times g(n) = \sum_{d|n}f(n) \cdot g(\frac{n}{d}) = \sum_{d|n}f(\frac{n}{d}) \cdot g(n)$ 。
其中 $\times$ 为卷积运算，不懂卷积运算的可以去search一下，这里就不详细介绍了(QAQ)。

推论：

$\epsilon = I \times \mu => [n == 1] = \sum_{d|n}\mu(d)$
$\psi = Id \times \mu => \psi(n) = \sum_{d|n}\mu(d) \cdot \lfloor \frac{n}{d} \rfloor$

一、介绍

莫比乌斯函数及其反演同样是数论中的重要内容。

定义 $\mu$ 为莫比乌斯函数，
$\mu(n) = \begin{cases} &1, n = 1\\ &0, n含有平方及以上因子\\ &(-1)^k,k为n的质因子个数\\ \end{cases}$
这里的质因子个数指的是只出现过一次的质因子的个数，一旦某个质因子出现2次及以上，则 $\mu(n) = 0$ 。

莫比乌斯函数是积性函数，因此可根据 $\epsilon = I \times \mu$ 推导出 $\sum_{d|n}\mu(d)$
这个公式很重要，务必牢记！

莫比乌斯反演：
若 $\sum_{d|n}f(d)$ ，则 $\sum_{d|n}g(d) \cdot \mu(\frac{n}{d}) = \sum_{d|n}g(\frac{n}{d} \cdot \mu(d)$ ，反之亦然。

二、莫比乌斯函数的算法求解

由于莫比乌斯函数的定义和性质，可利用欧拉线性筛求出 $\mu(x)$ ，时间复杂度为 $O (n)$ ：

//求n以内的莫比乌斯函数
int mu[N];
void mobius(int n)
{bitset<N> vis;//素数筛子vector<int> ps;//素数数组vis[0] = vis[1] = true;mu[1] = 1;for(int i = 2;i <= n;i++){if(!vis[i])ps.push_back(i),mu[i] = -1;//枚举素数表for(int j = 0;j < (int)ps.size() && i * ps[j] <= n;j++){vis[i * ps[j]] = true;//筛掉if(i % ps[j] == 0){mu[i * ps[j]] = 0;break;  } mu[i * ps[j]] = -mu[i];}}
}

三、例题

1、【模板】莫比乌斯反演
题目描述： $给定三个整数x,y,d,求解：\sum_{i=1}^{x}\sum_{j=1}^{y}[gcd(i,j) == d]。其中包含T（1 \leq T \leq 1000）组测试样例，每组测试样例三个整数x,y,d（1 \leq \sum x,\sum y,d \leq 10^5）。$

题目分析：

由题给公式可以推出 $\sum_{i=1}^{\lfloor \frac{x}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{y}{d} \rfloor}[gcd(i,j) == 1]$ ，由莫比乌斯反演可将公式推导为

$\sum_{i=1}^{\lfloor \frac{x}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{y}{d} \rfloor} \sum_{k|gcd(i,j)}\mu(k)$

$\sum_{k=1}^{min(\frac{x}{d},\frac{y}{d})}\mu(k) \sum_{i=1}^{\lfloor \frac{x}{d} \rfloor}[k|i]\sum_{j=1}^{\lfloor \frac{y}{d} \rfloor}[k|j]$

$\sum_{k=1}^{min(\frac{x}{d},\frac{y}{d})} \mu(k)\cdot \lfloor \frac{\lfloor \frac{x}{d} \rfloor}{k} \rfloor \cdot \lfloor \frac{\lfloor \frac{y}{d} \rfloor}{k} \rfloor$

题解：

//Code Here.
#include <bits/stdc++.h>
using namespace std;
#define int long longconst int N = 1e5 + 9;//求n以内的莫比乌斯函数
int mu[N];
void mobius(int n)
{bitset<N> vis;//素数筛子vector<int> ps;//素数数组mu[1] = 1;for(int i = 2;i <= n;i++){if(!vis[i])ps.push_back(i),mu[i] = -1;//枚举素数表for(int j = 0;j < (int)ps.size() && i * ps[j] <= n;j++){vis[i * ps[j]] = true;//筛掉if(i % ps[j] == 0){mu[i * ps[j]] = 0;break;  } mu[i * ps[j]] = -mu[i];}}
}signed main()
{mobius(N - 1);//预处理，求出u(x)int t;cin >> t;while(t--){int x,y,d;cin >> x >> y >> d;int res = 0;int n = x / d,m = y / d;for(int i = 1;i <= min(n,m);i++){res += mu[i] * (n / i) * (m / i);}cout << res << '\n';}
}

2、公约数的和

题目描述： $给定n，求解\sum_{i=1}^{n} \sum_{j=i+1}^{n} gcd(i,j)，结果对10^9 + 7取模。其中包含T（1 \leq T \leq 1000）组测试样例，每组测试样例一个整数n（1 \leq n \leq 10^6）。$

题目分析：此题稍难，只给出简单公式推导（QAQ）

$\sum_{i=1}^{n} \sum_{j=i+1}^{n} gcd(i,j) = \frac{\sum_{i=1}^{n} \sum_{j=1}^{n} gcd(i,j) - \sum_{i=1}gcd(i,i)}{2}$

$\sum_{i=1}^{n} \sum_{j=1}^{n} gcd(i,j) = \sum_{t=1}^{n}\psi(t) \cdot (\lfloor \frac{n}{t} \rfloor)^2$
题解：

//Code Here.
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
const int p = 1e9 + 7;const int N = 1e6 + 9;ll qmi(ll a,ll b)//快速幂((a^b)modc)
{ll res = 1;while(b){if(b & 1)res = res * a % p;a = a * a % p;b >>= 1;}return res;
}
int mo(int x){return (x % p + p) % p;}//欧拉筛求n以内的欧拉函数
ll phi_euler[N];
void _phi_euler(int n)
{bitset<N> vis;//素数筛子vector<int> ps;//素数数组phi_euler[1] = 1;for(int i = 2;i <= n;i++){if(!vis[i])ps.push_back(i),phi_euler[i] = i - 1;//枚举素数表for(int j = 0;j < (int)ps.size() && i * ps[j] <= n;j++){vis[i * ps[j]] = true;//筛掉if(i % ps[j] == 0){phi_euler[i * ps[j]] = phi_euler[i] * ps[j];break;  } phi_euler[i * ps[j]] = phi_euler[i] * phi_euler[ps[j]];}}for(int i = 1;i <= n;i++)phi_euler[i] = mo(phi_euler[i] + phi_euler[i - 1]);
}signed main()
{_phi_euler(N - 1);int inv2 = qmi(2,p - 2);int t;cin >> t;while(t--){int n;cin >> n;int res = 0;for(int l = 1,r = 1;l <= n;l = r + 1){r = min(n,n / (n / l));res = mo(res + mo(phi_euler[r] - phi_euler[l - 1]) * mo(n / l) % p * mo(n / l) % p);}int resn = mo(n * (n + 1) % p * inv2);cout << mo(mo(res - resn) * inv2) << '\n';}}

文章目录

一、介绍

二、莫比乌斯函数的算法求解

三、例题

相关文章：