数论函数/莫比乌斯反演

1.1积性函数

数论函数：可以认为是定义在整数上的函数。

1)积性函数定义

(a,b) = 1,f(a,b) = f(a)f(b)

2)积性函数性质

对于积性函数$f$，是被所有$p^e$处的值决定的

a = 1,f(b) = f(1)f(b)

$f(60) = f(4)\times f(15) = f(4)\times f(3)\times f(5)$

$n = \prod p^{ei}$

$f(n) = \prod f(pi^{ei})$

对于$f(4)$的话就没有办法把它表示成更小的素数幂的形式了，因为$4 = 2\times 2$显然$2$和$2$不互质

(重要！)积性函数$\times$积性函数还是积性函数

1.2 、完全积性函数

1)定义

f(a,b) = f(a)f(b) 不要求(a,b) = 1

$n = \prod p^{ei}$

$f(n) = \prod f(pi)^{ei}$

$f(x) = 1$
$f(x) = x$ $f(x) = \sqrt{x}$ $f(x) = x^2$
$ y= \begin{cases} 1,\quad x= 1\\ 0, \quad x\neq 1 \end{cases} \tag{1} $

1.3常见积性函数

①$id(x) = x$

②常数函数$I(x) = 1$

③单位函数$$ e(x)= \begin{cases} 1, \quad x= 1\\ 0, \quad x\neq 1 \end{cases} $$
$=[x = 1](bool)$

④欧拉函数$\phi(n) = n\prod_{p|n}(1-\dfrac{1}{p})$

$\phi(p^e) = (1-\dfrac{1}{p})*p^e = p^e-p^{e-1}$

⑤因子函数$d(n)$因子个数

$d(p^e) = e+1$ $(p^0p^1...p^e)$

⑥$\sigma(n)$因子和

$\sigma(p^e) = p^0+p^1+...+p^e = \dfrac{p^{e+1}-1}{p-1}$

⑦$\mu(n)$莫比乌斯函数

1.4 莫比乌斯函数

\[\mu(p^e)= \begin{cases} 1,\quad e= 0\\ 0, \quad e= 1 \\ 0 ,e\geq2\end{cases} \tag{1} \]

\[\mu(n)= \begin{cases} 1,\quad n= 1\\ (-1)^k, \quad n = p1p2...pk \\ 0 ,n有平方因子\end{cases} \tag{1} \]

1	2	3	4	5	6	7	8	9	10
1	-1	-1	0	-1	1	-1	0	0	1

性质：

$\sum_{d|n}\mu(d) = \begin{cases} 1,\quad n=1\\\ 0, \quad n\neq 1\end{cases} \tag{1}$

即：$\sum_{d|n}\mu(d) = e(n),\mu*1 = e$

1.5线性筛求积性函数

线性筛：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn =1000010;
bool is_pri[maxn];
int pri[maxn];
int cnt;

void init(int n)
{
	memset(is_pri, true, sizeof(is_pri));
	is_pri[1] = false;
	cnt = 0;
	for (int i = 2; i <= n; i++)
	{
		if (is_pri[i])
			pri[++cnt] = i;
		for (int j = 1; j <= cnt && i * pri[j] <= n; j++)
		{
			is_pri[i * pri[j]] = false;
			if (i % pri[j] == 0)break;            
		}
	}
}

由于一个正整数(除$1$外)可以通过质因数分解得到，对于非$1$的正整数都有：

$n = p_1^{e_1}*p_2^{e_2}*...*p_k^{e_k}$

根据积性函数定义，对于一个积性函数$f(n)$有:

$f(n) = f(p_1^{e1})\times f(p_2^{e2})\times ...\times f(p_k^{ek}) = \prod f(p_i^{ei})$
也就是说我们可以根据质因子推导出由该因子组成的合数。

对于一个合数有:

$f(n) = f(p_1^{e1})\times f(\dfrac{n}{p_1^{e1}})$

我们可以用线性筛帮助我们在$O(n)$求出$n$以内的积性函数值

定义：$p[i]为i$的最小质因子，$pr[cnt]$记录当前筛出的$cnt$个质数,$pe[i]$是$p_1^{e_1}$的值(标准分解里面的第一项)

求出$pe[i]$.
若$i\neq pe[i]$说明是合数，我们直接递推$f(i) = f(pe[i])\times f(\dfrac{i}{pe[i]})$

若$i = pe[i]$刚好是素数幂次，一般能从$p^{e-1}$推出$p^e$

因子个数：$d(p^e) = d(p^{e-1})+1$

因子和：$\sigma(p^e) = \sigma(p^e-1)+p^e$

欧拉函数：$\phi(p^e) = \dfrac{i}{p_i}*(p_{i}-1)$

莫比乌斯函数：$ \mu(i)= \begin{cases} -1,\quad i= p[i]
\\ 0\end{cases} \tag{1} $

void init(int n)//求各个函数的最小素数因子和指数
{
   p[1] = 1;
   for(int i = 2;i<=n;i++)
   {
   	if(!p[i])p[i] = i,pe[i] = i,pr[++cnt] = i;
   	for(int j = 1;j<=cnt&&pr[j]*i<=n;j++)
   	{
   		p[i*pr[j]] = pr[j];
   		if(p[i]==pr[j])//i和i*pr[j]的最小的素因子是一样的
            {
               //比如pe[5^3*7] = pr[5^2*7]*5
   			pe[i*pr[j]] = pe[i]*pr[j];
   			break;
   		}
   		else//说明被更小的质因子筛到了
   		{
   			pe[i*pr[j]] = pr[j];
   		}
		}
   } 
}

//写法1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn =1000010;
int p[maxn],pr[maxn/5],pe[maxn];
int cnt;

void init(int n)//求各个函数的最小素数因子和指数
{
	p[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(!p[i])p[i] = i,pe[i] = i,pr[++cnt] = i;
		for(int j = 1;j<=cnt&&pr[j]*i<=n;j++)
		{
			p[i*pr[j]] = pr[j];
			if(p[i]==pr[j])//i和i*pr[j]的素因子是一样的
			{
				pe[i*pr[j]] = pe[i]*pr[j];
				break;
			}
			else
			{
				pe[i*pr[j]] = pr[j];
			}
 		}
	}
}

uint f[N],a,b,ans;


void compute(int n,function<void(int)>calcpe){
	ans = 0;
	f[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(i==pr[i])calcpe(i);
		else f[i] = f[pe[i]]*f[i/pe[i]];//积性函数，把这两个乘起来
	}
	for(uint i = 1;i<=n;i++)
		ans ^= (a*i*f[i]+b);
	cout<<ans<<endl;
}


int main()
{
	cin>>n>>a>>b;
	init(n);

	//因子个数
	ans = 0;
	f[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(i==pe[i])
			f[i] = f[i/p[i]]+1;//i/p[i]==>p^{e-1}
		else f[i] = f[pe[i]]*f[i/pe[i]];//积性函数，把这两个乘起来
	}
	for(uint i = 1;i<=n;i++)
		ans ^= (a*i*f[i]+b);
	cout<<ans<<endl;

	//因子和
	ans = 0;
	f[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(i==pe[i])f[i] = f[i/p[i]]+i;
		else f[i] = f[pe[i]]*f[i/pe[i]];
	}
	for(uint i = 1;i<=n;i++)
		ans ^= (a*i*f[i]+b);
	cout<<ans<<endl;


	//欧拉函数
	ans = 0;
	f[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(i==pe[i])f[i] = i/p[i]*(p[i]-1);
		else f[i] = f[pe[i]]*f[i/pe[i]];
	}
	for(uint i = 1;i<=n;i++)
		ans ^= (a*i*f[i]+b);
	cout<<ans<<endl;

	//莫比乌斯函数
	ans = 0;
	f[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(i==pe[i]){
			if(i==p[i])f[i] = (uint)(-1);
			else f[i] = 0;
		}else f[i] = f[pe[i]]*f[i/pe[i]];
	}
	for(uint i = 1;i<=n;i++)
		ans ^= (a*i*f[i]+b);
	cout<<ans<<endl;
	return 0;
}

//写法2
#include<bits/stdc++.h>
using namespace std;
const int maxn =20010000;
int p[maxn],pr[maxn/5],pe[maxn];
int cnt;

void init(int n)//求各个函数的最小素数因子和指数
{
	p[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(!p[i])p[i] = i,pe[i] = i,pr[++cnt] = i;
		for(int j = 1;j<=cnt&&pr[j]*i<=n;j++)
		{
			p[i*pr[j]] = pr[j];
			if(p[i]==pr[j])//i和i*pr[j]的素因子是一样的
			{
				pe[i*pr[j]] = pe[i]*pr[j];
				break;
			}
			else
			{
				pe[i*pr[j]] = pr[j];
			}
 		}
	}
}

//如果单求phi
int phi[maxn];
void phi(int n)
{
	p[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(!p[i])p[i] = i,phi[i] = i-1,pr[++cnt] = i;
		for(int j = 1;j<=cnt&&i*pr[j]<=n;j++)
		{
			p[i*pr[j]] = pr[j];
			if(p[i]==pr[j])
			{
				phi[i*pr[j]] = phi[i]*pr[j];
				break;
			}else{
				phi[i*pr[j]] = phi[i]*(pr[j]-1);
			}
		}
	}
}

unsigned int f[maxn],a,b,ans,n;


void compute(int n,function<void(int)>calcpe){
	ans = 0;
	f[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(i==pe[i])calcpe(i);
		else f[i] = f[pe[i]]*f[i/pe[i]];//积性函数，把这两个乘起来
	}
	for(int i = 1;i<=n;i++)
		ans ^= (a*(unsigned int)i*f[i]+b);
	cout<<ans<<endl;
}


int main()
{
	cin>>n>>a>>b;
	init(n);
	//因子个数
	compute(n,[&](int x){
		f[x] = f[x/p[x]] + 1;
	});

	//因子和
	compute(n,[&](int x){
		f[x] = f[x/p[x]] + x;
	});


	//欧拉函数
	compute(n,[&](int x){
		f[x] = x/p[x]*(p[x]-1);
	});

	//莫比乌斯函数
	compute(n,[&](int x){
		f[x] = x==p[x]?-1:0;
	});
	return 0;
}

2.1迪利克雷卷积

2.1.1定义

$h(n) = \sum_{d|n}f(d)g(\dfrac{n}{d}) = \sum_{d_1d_2 = n}f(d_1)g(d_2)$

✳常见函数

$e$是单位函数，$e(n)=[n=1]$ ， $e$ 满足 $f = f ∗ e$,即任何一个函数卷上$e$ 都等于原函数。

$I$是常数函数， $I ( n ) = 1$。
$Id$ 是恒等函数，$Id(n)=n$
$\mu$ 是莫比乌斯函数$$ \mu(n)= \begin{cases} 1,\quad n= 1\ (-1)^k, \quad n = p1p2...pk \ 0 ,n有平方因子\end{cases} \tag{1} $$

$ \phi$ 是欧拉函数，$ \phi(n)=\sum_{d\leq n}[gcd(d,n)=1]$欧拉函数就是小于 $n$ 的与它互质的数的个数。
$\sigma$是约数函数，$\sigma(n)=\sum_{d|n}d$
$ d$ ，约数函数就是$ n$ 的约数和。

✳迪利克雷卷积函数

将上述数论函数两两做卷积，可以得到一些新的数论函数：

除数函数与幂函数

欧拉函数与恒等函数

2.1.2性质

符合交换律和结合律
(重要)$f$和$g$是积性函数=>$f*g$是积性函数

3.1莫比乌斯反演

莫比乌斯函数：

\[\mu(n)= \begin{cases} 1,\quad n= 1\\ (-1)^k, \quad n = p1p2...pk(奇数个质因子-1，偶数个就是1) \\ 0 ,n有平方因子\end{cases} \tag{1} \]

性质：

$\sum_{d|n}\mu(d) = \begin{cases} 1,\quad n=1\\\ 0, \quad n\neq 1\end{cases} \tag{1}$

即：$\sum_{d|n}\mu(d) = e(n),\mu*1 = e$

3.1.1形式

$f(n) = \sum_{n|d}g(d)=>g(n)= \sum \mu(\dfrac{n}{d})f(d)$

$g = f*\mu$

$1*\mu = e$即：$\sum_{d|n}\mu(d) = \begin{cases} 1,\quad n=1\\\ 0, \quad n\neq 1\end{cases} \tag{1}$

证明：

$f(p^e) = \sum_{d|p^e} = \sum_{d|p^e}\mu(d)$

$e>=1$，$f(p^e) = \mu(1)+\mu(p)+\mu(p^2)+...+\mu(p^e)$

$\mu(1) = 1,\mu(p) = -1$，后面都等于$0$

所以对于任何$e$不等于1的值都是0

$\because f = f*e,f = g*1$

在两边同乘一个$\mu$得：$f*\mu = (g*1)*\mu =>f*\mu = g*(1*\mu)$

又因为$1*\mu = e，g*e = g$，所以$f*\mu = g$

$g(n) = \sum_{d|n}f(d)*\mu(\frac{n}{d})$

$f*(\mu*1) = g*1=>f*e = g=>f =g$

即可以推出：$f(n) = \sum_{d|n}g(d)$

3.1.2莫比乌斯反演公式

约数的莫比乌斯反演：
若：$f(n) = \sum_{d|n}g(d)$

则：$g(n) = \sum_{d|n}\mu(d)f(\dfrac{n}{d})$

倍数的莫比乌斯反演：
若：$f(n) = \sum_{d|n}g(d)$
则：$g(n) = \sum_{d|n}\mu(\dfrac{n}{d})f(d)$

3.1.3构造

典例：求$\sum_{i = 1}^{n}\sum_{j = 1}^{m}[gcd(i,j)==d]$

不妨记$g(x) = \sum_{i = 1}^{n}\sum_{j = 1}^{m}[\gcd(i,j)==d]$

任何让我们构造一个$f(x)$，这里我们需要用到第二组莫比乌斯反演公式。

那么$f(x)$是什么嘞？根据公式可知是若干个$g(x)$的和。记$N = min(n,m)$，即$\gcd$的上限，我们可以得到$f(d) = g(d)+d(2d)+g(3d)+...+g(\lfloor\dfrac{N}{d}\rfloor)$

即:$f(d) = \sum_{i = 1}^{n}\sum_{j = 1}^{m}[\gcd(i,j)\bmod d==0]$

写成公式形式就是：$g(d) = \sum_{d|p}\mu(\dfrac{p}{d})f(p)$

接下来问题就是如何求$f(x)$。$f(x)$是满足$\gcd(i,j)$是$d$的倍数的数对，显然有$f(x) = \lfloor\dfrac{n}{x}\rfloor\lfloor\dfrac{m}{x}\rfloor$

$g(n) = \sum_{d = 1}^{n}\mu(\dfrac{n}{d})*f(d)$

eg.莫比乌斯反演

题意：

给定一个函数$f(1),f(2),…,f(n)，$已知$f(n)=\sum_{d|n}g(d)$，求$g(1),g(2),…,g(n)$。

思路：

\[\mu(n)= \begin{cases} 1,\quad n= 1\\ (-1)^k, \quad n = p1p2...pk \\ 0 ,n有平方因子\end{cases} \tag{1} \]

$f(n) = \sum_{n|d}g(d)=>g(n)= \sum \mu(\dfrac{n}{d})f(d)$

$f = g*\mu$

#include<bits/stdc++.h>
using namespace std;
const int N = 1E6+10;
unsigned int A,B,C;
int n,cnt,f[N],p[N],mu[N],pr[N],g[N];
inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}
int main(){
    scanf("%d%u%u%u", &n, &A, &B, &C);
    for (int i = 1; i <= n; i++)
        f[i] = rng61();
    p[1] = 1,mu[1] = 1;
    for(int i = 2;i<=n;i++)
    {
        if(!p[i])p[i] = i,mu[i] = (unsigned int)-1,pr[++cnt] = i;
        for(int j = 1;j<=cnt&&pr[j]*i<=n;j++)
        {
            p[i*pr[j]] = pr[j];
            if(p[i]==pr[j])
            {
                mu[i*pr[j]] = 0;
                break;
            }
            else
                mu[i*pr[j]] = (unsigned int)-mu[i];
        }
    }
    //g = f*mu
    //g[n] = sum_{d|n} f[d]*mu[n/d]
    //g[n] = sum_{n = d1*d2} f[d1]*mu[d2]
    for(int d1 = 1;d1<=n;d1++)
        for(int d2 = 1;d1*d2<=n;d2++)
            g[d1*d2] += f[d1]*mu[d2];
    unsigned int ans = 0;
    for(int i = 1;i<=n;i++)ans^=g[i];
    cout<<ans<<endl;
}

法二：

$f(n) = \sum_{d|n}g(d)$

$g(i) = f(i)-\sum_{d|i,d\neq i}g(d)$

eg2互质数对

题意：

$T$组询问，每次给两个数$n,m$，求有多少对$(i,j)$满足1$≤i≤n,1≤j≤m$并且$i,j$互质。

思路：

$\sum_{i<=i<=n,1<=j<=m}[(i,j)==1]=\sum e((i,j))$

$e(n) = [n==1]$

$e = 1*\mu$

$e(n) = \sum_{d|n}\mu(d)$

$1*\mu = e$即：$\sum_{d|n}\mu(d) = \begin{cases} 1,\quad n=1\\\ 0, \quad n\neq 1\end{cases} \tag{1}$

$\sum_{i=1}^{n}\sum_{j = 1}^{m}[\gcd(i,j)==1]$

$=\sum e((i,j)) = \sum_{i,j}\sum_{d|(i,j)}\mu(d)$

我们把$\gcd(i,j)$转化为$d|i$且$d|j$

$ = \sum_{i=1}^{n}\sum_{j = 1}^{m}\mu(d)[d|i][d|j]$

$ = \sum_{d = 1}^{n}\mu(d)\sum_{j = 1}^{m}[d|i][d|j]$

$=\sum_{d = 1}^{n}\mu(d)\lfloor\dfrac{n}{d}\rfloor\lfloor\dfrac{m}{d} \rfloor$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10100000, M = 10000000;
int p[N],pr[N/5],n,cnt;
int mu[N],smu[N];
int main()
{
    p[1] = 1,mu[1] = 1;
    for(int i = 2;i<=M;i++)
    {
        if(!p[i])p[i] = i,mu[i] = -1,pr[++cnt] = i;
        for(int j = 1;j<=cnt&&i*pr[j]<=M;j++)
        {
            p[i*pr[j]] = pr[j];
            if(p[i]==pr[j])
            {
                mu[i*pr[j]] = 0;
                break;
            }else{
                mu[i*pr[j]] = -mu[i];
            }
        }
    }
    for(int i = 1;i<=M;i++)
        smu[i] = smu[i-1]+mu[i];
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        if(n>m)swap(n,m);
        ll ans = 0;
        //for(i~n)因为如果for(1~m)的话,n/l就已经是0了
        for(int l = 1;l<=n;l++)
        {
            int r = min(n/(n/l),m/(m/l));//在[l,r]里面n/l和m/l都是不变的
            ans += 1ll*(smu[r]-smu[l-1])*(n/l)*(m/l);
            l = r;
        }
        cout<<ans<<endl;
    }
    return 0;
}

eg3.gcd之和

题意：

T组询问，每次给两个数$n,m$，求$\sum_{i = 1}^{n}\sum_{j = 1}^{m}(i,j)$

思路：

\[\mu(n)= \begin{cases} 1,\quad n= 1\\ (-1)^k, \quad n = p1p2...pk \\ 0 ,n有平方因子\end{cases} \tag{1} \]

性质：$\sum_{d|n}\mu(d) = \begin{cases} 1,\quad n=1\\\ 0, \quad n\neq 1\end{cases} \tag{1}$

$id*\mu = \phi$

$\sum_{d|n}\phi(d) = n$

$\sum_{d|p^e}\mu(d)(\dfrac{p^e}{d})$

只有当$d = 1和d = p$的时候有值，其他都是0

$d = 1时，\mu(d) = 1,d = p时，\mu(d) = -1$

$p^e-p^{e-1} = \phi(p^e)$

所以：$\sum_{i = 1}^{n}\sum_{j = 1}^{m}(i,j) = \sum_{d = 1}^{n}\phi(d)\lfloor\dfrac{n}{d}\rfloor\lfloor\dfrac{m}{d}\rfloor$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10100000, M = 10000000;
ll p[N],pr[N/5],n,cnt;
ll phi[N],sphi[N];
int main()
{
    p[1] = 1,phi[1] = 1;
    for(int i = 2;i<=M;i++)
    {
        if(!p[i])p[i] = i,phi[i] = i-1,pr[++cnt] = i;
        for(int j = 1;j<=cnt&&i*pr[j]<=M;j++)
        {
            p[i*pr[j]] = pr[j];
            if(p[i]==pr[j])
            {
                phi[i*pr[j]] = phi[i]*pr[j];
                break;
            }else{
                phi[i*pr[j]] = phi[i]*(pr[j]-1);
            }
        }
    }
    for(int i = 1;i<=M;i++)
        sphi[i] = sphi[i-1]+phi[i];
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        if(n>m)swap(n,m);
        ll ans = 0;
        //for(i~n)因为如果for(1~m)的话,n/l就已经是0了不用算了
        for(int l = 1;l<=n;l++)
        {
            int r = min(n/(n/l),m/(m/l));//在[l,r]里面n/l和m/l都是不变的
            ans += 1ll*(sphi[r]-sphi[l-1])*(n/l)*(m/l);
            l = r;
        }
        cout<<ans<<endl;
    }
    return 0;
}

✳总结做题技巧

对于所有带$\gcd$的

$\sum_{i = 1}^{n}\sum_{j = 1}^{m}f((i,j))$

对于以上我们都能找到数论函数$g$满足$f(n) = \sum_{d|n}g(d)$,即$g = f*\mu$

$f((i,j)) = \sum_{d|(i,j)}g(d)$

我们把$d$提出来

$\sum_dg(d)\sum_{1<=i<=n,1<=j<=m,d|i,d|j}1 $

$= \sum_{d}g(d)\lfloor\dfrac{n}{d}\rfloor\lfloor\dfrac{m}{d}\rfloor$

以上方法对所有带$\gcd$的均适用

JZTXT

[数论]数论函数/莫比乌斯反演

数论函数/莫比乌斯反演

1.1积性函数

1)积性函数定义

2)积性函数性质

1.2 、完全积性函数

1)定义

1.3常见积性函数

1.4 莫比乌斯函数

1.5线性筛求积性函数

2.1迪利克雷卷积

2.1.1定义

✳常见函数

✳迪利克雷卷积函数

除数函数与幂函数

欧拉函数与恒等函数

2.1.2性质

3.1莫比乌斯反演

3.1.1形式

3.1.2莫比乌斯反演公式

3.1.3构造

eg.莫比乌斯反演

eg2互质数对

eg3.gcd之和

✳总结做题技巧