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

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

• 常见数论函数分为两种：
  $$\{\begin{array}{ll}& 完全积性函数：对于任意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{array}$$
  常见的完全积性函数有：单位函数$ϵ(n)=[n==1]$，常数函数$I(n)==1$，恒等函数$Id(n)==n$等；
  常见的积性函数有：莫比乌斯函数$\mu (n)$，欧拉函数$\psi (n)$，约数和函数$\sigma (n)={\sum }_{d|n}d$等。

• 狄利克雷卷积定义：若$f(n),g(n)$均为数论函数，则$h(n)=f(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)。

推论：

• $ϵ=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{array}{ll}& 1,n=1\\ & 0,n含有平方及以上因子\\ & (-1{)}^k,k为n的质因子个数\end{array}$$
这里的质因子个数指的是只出现过一次的质因子的个数，一旦某个质因子出现2次及以上，则$\mu (n)=0$。

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

莫比乌斯反演：
  若$g(n)={\sum }_{d|n}f(d)$，则$f(n)={\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\le T\le 1000）组测试样例，每组测试样例三个整数x,y,d（1\le \sum x,\sum y,d\le 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 long

const 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\le T\le 1000）组测试样例，每组测试样例一个整数n（1\le n\le 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';
    }
    
}