数论函数/莫比乌斯反演
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\)的均适用
标签:函数,数论,sum,mu,反演,int,莫比,quad,cases From: https://www.cnblogs.com/nannandbk/p/17515322.html