2021.12.13 莫比乌斯反演
2021.12.13 莫比乌斯反演
https://blog.csdn.net/Ivanzn/article/details/88641049
https://zhuanlan.zhihu.com/p/197411920
1. 前置知识
1.1 组合等式
\[\binom{n}{0}-\binom{n}{1}+\binom{n}{2}-\cdots+(-1)^n\binom{n}{n}=0 \]组合意义：
\(n\) 个元素中取 \(r\) 个组合， \(r\) 为奇数的组合数目等于 \(r\) 为偶数的组合数目（包括 \(r=0\) ）。
证明：
把 \(r\) 为奇数的组合和 \(r\) 为偶数的组合一一对应。
把所有组合分成含元素 \(a\) 的和不含元素 \(a\) 的。设 \(r\) 为奇数，若含有元素 \(a\) ，则去掉 \(a\) 之后对应且唯一对应 \(r-1\) 为偶数的组合，若不含元素 \(a\) ，则加上 \(a\) 之后对应且唯一对应 \(r+1\) 为偶数的组合。当 \(r\) 为偶数时同理。
1.2 莫比乌斯函数
\[\mu(n)=\begin{cases} 1,&n=1\\ 0,&n含有平方素因子\\ (-1)^k,&n是k个互素因子的积 \end{cases} \]1.3 莫比乌斯函数衍生的定理（结论1）
\[对于任意正整数n，有\\ \sum_{d|n}\mu(d)=\begin{cases} 1,&n=1\\ 0,&n>1 \end{cases} \]证：
当 \(n=1\) 时，
\[\sum_{d|n}\mu(d)=\mu(1)=1 \]当 \(n>1\) 时，设 \(n=p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n}\) ， \(m=p_1p_2\cdots p_n\) ，则
\[\sum_{d|n}\mu(d)=\sum_{d|m}\mu(d)\\ =\binom{m}{0}*(-1)^0+\binom{m}{1}*(-1)^1+\binom{m}{2}*(-1)^2+\cdots+\binom{m}{m}*(-1)^m\\ =\binom{m}{0}-\binom{m}{1}+\binom{m}{2}-\cdots+(-1)^m\binom{m}{m}\\ =0 \]1.4 狄利克雷卷积
1.4.1 各种数论函数
以下三种数论函数全部都是完全积性函数。
单位元： \(\epsilon(x) = [x = 1]\) 。
常函数： \(1(x)=1\) 。
恒等函数： \(id(x)=x\) 。
以下两种数论函数为积性函数但不是完全积性函数。
除数函数： \(d(n)\) ，n的因数个数
除数和函数： \(\sigma(n)\) ，n的所有因数之和
以上两个函数可以和到一个函数中，这个函数也叫除数函数，想不到吧？/滑稽
\[\sigma_\lambda(n)=\sum_{d|n}d^\lambda \]当 \(\lambda=0\) 时， \(\sigma_0(n)=d(n)\) ；
当 \(\lambda=1\) 时， \(\sigma_1(n)=\sigma(n)\) 。
1.4.2 定义
对于两个数论函数 \(f\) 、 \(g\) ，若 \(t=f*g\) ，则
\[t(n)=\sum_{d|n}f(i)g(\frac{n}{i}) \]1.4.3 性质
交换律：
\[f*g=g*f \]结合律：
\[f*(g*h)=(f*g)*h \]分配律：
\[f*h+g*h=(f+g)*h \]数乘：
\[(xf)*g=x(f*g) \]单位元
\[f*\epsilon=f \]逆元：对于每一个 \(f(1)!=0\) 的函数 \(f\) ，都有 \(f*g=\epsilon\) 。 \(g\) 就是逆元。
2. 结论2
\[\sum_{i<=n}\sum_{d|i}\mu(d) \]原式先枚举 \(i\) ，再枚举 \(i\) 的所有因数 \(d\) ，等价于先枚举 \(d\) ，再枚举小于等于n的所有倍数。即
\[\sum_{i<=n}\sum_{d|i}\mu(d)=\sum_{d<=n}\lfloor\frac{n}{d}\rfloor\mu(d) \]3. 结论3
\[\sum_{i<=n}\sum_{j<=m}[(i,j)=1]\\ =\sum_{i<=n}\sum_{j<=m}\sum_{d|(i,j)}\mu(d)\\ =\sum_{i<=n}\sum_{j<=m}\sum_{d|i}\sum_{d|j}\mu(d)\\ =\sum_{i<=n}\sum_{d|i}\sum_{j<=m}\sum_{d|j}\mu(d)\\ =\sum_{i<=n}\sum_{d|i}\sum_{d<=m}\lfloor\frac{m}{d}\rfloor\mu(d)\\ =\sum_{d<=n}\lfloor\frac{n}{d}\rfloor\sum_{d<=m}\lfloor\frac{m}{d}\rfloor\mu(d)\\ =\sum_{d<=\min(n,m)}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\mu(d) \]4. 乱七八糟的推论
4.1 \(d*\mu=1\)
证明：
\[因为\sum_{d|n}\mu(d)1(\frac{n}{d})=\epsilon(n)，则\mu*1=\epsilon\\ 因为d(n)=\sum_{e|n}1(e)1(\frac{n}{e})，则d=1*1\\ d*\mu=1*1*\mu\\ d*\mu=1*\epsilon\\ 因为h(n)=\sum_{e|n}1(e)\epsilon(\frac{n}{e})=1(n)，则d*\mu=1 \]4.2 \(\phi*1=id\)
\[设w(T)=\sum_{t|T}\phi(t)*1(\frac{T}{t})\\ w(T)=\sum_{t|T}\phi(t)\\ =T\\ =id(T) \]4.3 \(id*\mu=\phi\)
证：
\[设h(T)=\sum_{t|T}id(t)*\mu(\frac{T}{t})\\ h=id*\mu\\ h*1=id*1*\mu\\ h*1=id*\epsilon\\ 设g(T)=\sum_{t|T}id(t)*\epsilon(\frac{T}{t})\\ g(T)=id(T)*\epsilon(1)=T\\ g=id\\ h*1=id\\ 因为\phi*1=id，则h=\phi\\ id*\mu=\phi \]5. 练习题
请注意：long long的速度比int慢！！！
https://www.luogu.com.cn/problem/P1390
题意：
\[\sum_{i=1}^{n}\sum_{j=i+1}^{n}(i,j) \]分析：
https://www.luogu.com.cn/blog/juruoHBr/solution-p1390
\[\sum_{i<=n}\sum_{j<=n}(i,j)\\ =\sum_{d<=n}d*\sum_{i<=n}\sum_{j<=n}[(i,j)=d]\\ =\sum_{d<=n}d*\sum_{i<=\frac{n}{d}}\sum_{j<=\frac{n}{d}}[(i,j)=1]\\ \]设 \(t=\frac{n}{d}\) ，则
\[原式=\sum_{d<=n}d*\sum_{e<=n}\lfloor\frac{t}{e}\rfloor*\lfloor\frac{t}{e}\rfloor*\mu(e) \]最后的结果减去 \((i,i)=i\) 的和 \((i,j)=(j,i)\) 。
\[\sum_{i<=n}(i,i)=\sum_{i<=n}i=\frac{(1+n)*n}{2} \]对于所有 \((i,j)=(j,i)\) ，只需要在减完上一条式子之后把答案除以2。
代码如下：
#include
#include
#include
#include
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define int long long
const int N=2e6+10;
int n,mu[N],is_prime[N],prime[N],top,sum[N];
inline void init(){
//for(int i=1;i<=n;i++)is_prime[i]=1;
mu[1]=1;
for(int i=2;i<=n;i++){
if(!is_prime[i])is_prime[i]=i,prime[++top]=i,mu[i]=-1;
for(int j=1;j<=top;j++){
if(prime[j]>is_prime[i]||i*prime[j]>n)break;
is_prime[i*prime[j]]=prime[j];
mu[i*prime[j]]=i%prime[j]?-mu[i]:0;
//如果 i%prime[j]==0 ，则说明至少含有两个相同素数
//否则就是 mu[i]*(-1)
}
}
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+mu[i];//,cout<>n;
init();
int ans=0;
for(int i=1;i<=n;i++)ans+=i*calc(n,i);
//cout< https://www.luogu.com.cn/problem/P6810
题意：
\[\sum_{1<=n}\sum_{j<=m}d(i)d(j)d((i,j)) \]分析：
https://www.luogu.com.cn/blog/genshy/solution-p6810
https://www.luogu.com.cn/blog/quest233/solution-p6810
要求 \(n<=m\) ，不满足要求你就 swap 一下，反正不亏。
令 \(T=ek\) ，则
\[原式=\sum_{T<=n}\sum_{k|T}d(k)\mu(\frac{T}{k})\sum_{i<=\frac{n}{T}}\sum_{j<=\frac{m}{T}}d(iT)d(jT)\\ =\sum_{T<=n}\sum_{i<=\frac{n}{T}}\sum_{j<=\frac{m}{T}}d(iT)d(jT)\\ \sum_{T<=n}\sum_{T|i}^{i<=n}\sum_{T|j}^{j<=m}d(i)d(j) \]代码如下：
#include
#include
#include
#include
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
//#define int long long
const int N=2e6+10;
int d[N],f[N];
long long sum1[N],sum2[N];
int n,m,mod,is_prime[N],prime[N],top;
inline void init(){
d[1]=f[1]=is_prime[1]=1;
for(int i=2;i<=m;i++){
if(!is_prime[i])prime[++top]=i,f[i]=1,d[i]=2;
for(int j=1;j<=top&&i*prime[j]<=m;j++){
is_prime[i*prime[j]]=1;
if(i%prime[j]==0){
f[i*prime[j]]=f[i]+1;
d[i*prime[j]]=1ll*d[i]*(f[i*prime[j]]+1)/(f[i]+1);
//此时最小质因子个数为f[i]+1，因为这是在i的基础上才新找到的最小质因子
//所以此时因数的个数为(d[i]/(f[i]+1))*(f[i*prime[j]]+1)
break;
}
f[i*prime[j]]=1;
d[i*prime[j]]=1ll*d[i]*d[prime[j]];
}
}
}
signed main(){
IOS;
cin>>n>>m>>mod;
if(n>m)swap(n,m);
init();
for(int i=1;i<=n;i++)for(int j=1;j<=n/i;j++)sum1[i]=(sum1[i]+d[i*j])%mod;
for(int i=1;i<=m;i++)for(int j=1;j<=m/i;j++)sum2[i]=(sum2[i]+d[i*j])%mod;
long long ans=0;
for(int i=1;i<=n;i++)ans=(ans+1ll*sum1[i]*sum2[i]%mod)%mod;
cout< https://www.luogu.com.cn/problem/P2257
题意：
\[\sum_{i<=n}\sum_{j<=m}[(i,j)是质数] \]分析：
设 \(p_1,p_2,p_3,\cdots,p_{top}\) 均为质数。
\[\sum_{i<=n}\sum_{j<=m}[(i,j)是质数]\\ =\sum_{d<=top}\sum_{i<=n}\sum_{j<=m}[(i,j)=p_d]\\ =\sum_{d<=top}\sum_{i<=\frac{n}{p_d}}\sum_{j<=\frac{m}{p_d}}[(i,j)=1]\\ =\sum_{d<=top}\sum_{i<=\frac{n}{p_d}}\sum_{j<=\frac{m}{p_d}}\sum_{k|(i,j)}\mu(k)\\ =\sum_{d<=top}\sum_{i<=\frac{n}{p_d}}\sum_{j<=\frac{m}{p_d}}\sum_{k|i}\sum_{k|j}\mu(k)\\ =\sum_{d<=top}\sum_{i<=\frac{n}{p_d}}\sum_{k|i}\sum_{j<=\frac{m}{p_d}}\sum_{k|j}\mu(k)\\ =\sum_{d<=top}\sum_{k<=\frac{n}{p_d}}\lfloor\frac{n}{p_dk}\rfloor\lfloor\frac{m}{p_dk}\rfloor\mu(k) \]令 \(T=p_dk\) ，则
\[原式=\sum_{d<=top}\sum_{k<=\frac{n}{T}}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\mu(\frac{T}{p_d})\\ =\sum_{d<=top}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{k<=\frac{n}{T}}\mu(\frac{T}{p_d})\\ =\sum_{T<=n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{t|T}\mu(t) \]代码如下：
#include
#include
#include
#include
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define int long long
typedef long long ll;
const int N=1e7+10;
int t,m,n,mu[N],is_prime[N],prime[N],top;
ll sum[N],tot[N];
inline void init(){
mu[1]=1;
for(int i=2;i<=N-10;i++){
if(!is_prime[i])prime[++top]=i,mu[i]=-1;
for(int j=1;j<=top&&i*prime[j]<=N-10;j++){
is_prime[i*prime[j]]=1;
if(i%prime[j]==0)break;
else mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<=top;i++)for(int j=1;j*prime[i]<=N-10;j++)tot[j*prime[i]]+=1ll*mu[j];
//for(int i=1;i<=10;i++)cout<>t;
while(t--){
cin>>n>>m;
if(n>m)swap(n,m);
ll ans=0;
for(int L=1,R=0;L<=n;L=R+1){
R=min(n/(n/L),m/(m/L));
ans+=(n/L)*(m/L)*(sum[R]-sum[L-1]);
}
cout< https://www.luogu.com.cn/problem/P2522
题意：
\[\sum_{i=a}^{b}\sum_{j=c}^{d}[(i,j)=k] \]分析：
行吧，2021.12.12号考试是我傻，都推到第二步了愣是没想到莫比乌斯反演 ，无语中……
\[\sum_{i<=b}\sum_{j<=d}[(i,j)=k]\\ =\sum_{i<=\frac{b}{k}}\sum_{j<=\frac{d}{k}}[(i,j)=1]\\ =\sum_{i<=\frac{b}{k}}\sum_{j<=\frac{d}{k}}\sum_{e|i}\sum_{e|j}\mu(e)\\ =\sum_{e<=\frac{b}{k}}\lfloor\frac{b}{ke}\rfloor\lfloor\frac{d}{ke}\rfloor\mu(e) \]代码如下：
#include
#include
#include
#include
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int N=5e4+10;
int t,mu[N],is_prime[N],prime[N],top;
ll sum[N];
inline void init(){
mu[1]=1;
for(int i=2;i<=N-10;i++){
if(!is_prime[i])prime[++top]=i,mu[i]=-1;
for(int j=1;j<=top&&i*prime[j]<=N-10;j++){
is_prime[i*prime[j]]=1;
if(i%prime[j]==0)break;
else mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<=N-10;i++)sum[i]=sum[i-1]+1ll*mu[i];
//for(int i=1;i<=10;i++)cout<m)swap(n,m);
for(int L=1,R=0;L<=n;L=R+1){
R=min(n/(n/L),m/(m/L));
ans+=1ll*(m/L)*(n/L)*(sum[R]-sum[L-1]);
}
return ans;
}
signed main(){
IOS;
init();
cin>>t;
while(t--){
int a,b,c,d,k;
cin>>a>>b>>c>>d>>k;
ll ans=solve(b,d,k)-solve(b,c-1,k)-solve(a-1,d,k)+solve(a-1,c-1,k);
cout< https://www.luogu.com.cn/problem/P1447
题意：
\[2*\sum_{i<=n}\sum_{j<=m}(i,j)-n*m \]分析：
\[2*\sum_{i<=n}\sum_{j<=m}(i,j)-n*m\\ =2*\sum_{d<=n}d*\sum_{i<=n}\sum_{j<=m}[(i,j)=d]-n*m\\ =2*\sum_{d<=n}d*\sum_{i<=\frac{n}{d}}\sum_{j<=\frac{m}{d}}[(i,j)=1]-n*m\\ =2*\sum_{d<=n}d*\sum_{i<=\frac{n}{d}}\sum_{j<=\frac{m}{d}}\sum_{k|(i,j)}\mu(k)-n*m\\ =2*\sum_{d<=n}d*\sum_{i<=\frac{n}{d}}\sum_{j<=\frac{m}{d}}\sum_{k|i}\sum_{k|j}\mu(k)-n*m\\ =2*\sum_{d<=n}d*\sum_{k<=\frac{n}{d}}\lfloor\frac{n}{dk}\rfloor\lfloor\frac{m}{dk}\rfloor\mu(k)-n*m\\ =2*\sum_{d<=n}\sum_{k<=\frac{n}{d}}\lfloor\frac{n}{dk}\rfloor\lfloor\frac{m}{dk}\rfloor d*\mu(k)-n*m \]令 \(T=dk\) ，则
\[原式=2*\sum_{T<=n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{t|T}\mu(t)*\frac{T}{t}\\ =2*\sum_{T<=n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\phi(T) \]代码如下：
#include
#include
#include
#include
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define int long long
const int N=1e5+10;
int n,m,top,is_prime[N],prime[N];
long long phi[N],sum[N];
inline void init(){
phi[1]=1;
for(int i=2;i<=m;i++){
if(!is_prime[i])prime[++top]=i,phi[i]=i-1;
for(int j=1;j<=top&&i*prime[j]<=m;j++){
is_prime[i*prime[j]]=1;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
for(int i=1;i<=m;i++)sum[i]=sum[i-1]+phi[i];
//for(int i=1;i<=m;i++)cout<>n>>m;
if(n>m)swap(n,m);
init();
long long ans=0;
for(int L=1,R=0;L<=n;L=R+1){
R=min(n/(n/L),m/(m/L));
ans+=1ll*(n/L)*(m/L)*(sum[R]-sum[L-1]);
}
cout< https://www.luogu.com.cn/problem/P1829
题意：
\[\sum_{i<=n}\sum_{j<=m}lcm(i,j) \]分析：
\[\sum_{i<=n}\sum_{j<=m}lcm(i,j)\\ =\sum_{i<=n}\sum_{j<=m}\frac{ij}{(i,j)}\\ =\sum_{d<=n}\sum_{i<=n}\sum_{j<=m}[(i,j)=d]\frac{ij}{d}\\ =\sum_{d<=n}\sum_{i<=\frac{n}{d}}\sum_{j<=\frac{m}{d}}[(i,j)=1]\frac{ijd^2}{d}\\ =\sum_{d<=n}\sum_{i<=\frac{n}{d}}\sum_{j<=\frac{m}{d}}ijd\sum_{k|(i,j)}\mu(k)\\ =\sum_{d<=n}d\sum_{i<=\frac{n}{d}}\sum_{j<=\frac{m}{d}}ij\sum_{k|(i,j)}\mu(k)\\ =\sum_{d<=n}d\sum_{k<=\frac{n}{d}}\sum_{k|i}^{i<=n}\sum_{k|j}^{j<=m}\mu(k)ij\\ =\sum_{d<=n}d\sum_{k<=\frac{n}{d}}\mu(k)k^2\sum_{i<=\frac{n}{k}}\sum_{j<=\frac{m}{k}}ij\\ =\sum_{d<=n}d\sum_{k<=\frac{n}{d}}\mu(k)k^2*\frac{(1+\frac{n}{k})\frac{n}{k}}{2}*\frac{(1+\frac{m}{k})\frac{m}{k}}{2} \]代码如下：
#include
#include
#include
#include
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define int long long
const int N=1e7+10;
const int mod=20101009;
int n,m,top,is_prime[N],prime[N];
long long mu[N],sum[N];
inline void init(){
mu[1]=1;
for(int i=2;i<=m;i++){
if(!is_prime[i])prime[++top]=i,mu[i]=-1;
for(int j=1;j<=top&&i*prime[j]<=m;j++){
is_prime[i*prime[j]]=1;
if(i%prime[j]==0)break;
else mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<=m;i++)sum[i]=(sum[i-1]+1ll*(mu[i]+mod)%mod*i%mod*i%mod)%mod;
}
inline int func(int x,int y){
return 1ll*((1+x)*x/2%mod)*((1+y)*y/2%mod)%mod;
}
inline int calc(int x,int y){
int fin=0;
for(int L=1,R=0;L<=min(x,y);L=R+1){
R=min(x/(x/L),y/(y/L));
fin=(fin+1ll*((sum[R]-sum[L-1])%mod)*(func(x/L,y/L)%mod))%mod;
}
return fin;
}
signed main(){
IOS;
cin>>n>>m;
if(n>m)swap(n,m);
init();
long long ans=0;
for(int L=1,R=0;L<=n;L=R+1){
R=min(n/(n/L),m/(m/L));
ans=(ans+1ll*((L+R)*(R-L+1)/2%mod)*calc(n/L,m/L)%mod+mod)%mod;
}
cout<