-
\(x|y:\) \(x\) 是 \(y\) 的因数。
-
\([S]:\) 若 \(S\) 为真，\([S]=1\)，若 \(S\) 为假，则 \([S]=0\)（如 \([gcd(11,45)=14]=0\)）。
-
\(\sum:\) 求和符号。
-
\(\prod:\) 连乘符号。
-
\(n=\prod\limits_{i=1}^{k}p_i^{q_i}:\) 将 \(n\) 分解质因数。即默认 \(p_i\) 两两不同且为质数。
先介绍 \(\mu\) 函数：
-
\(\mu(1)=1\)。
-
若 \(i\) 含有平方因子，\(\mu(i)=0\)。
-
若 \(i\) 为奇数个不同的质因数的乘积，\(\mu(i)=-1\)。
-
若 \(i\) 为偶数个不同的质因数的乘积，\(\mu(i)=1\)。
容易发现，\(\mu\) 可以进行线性筛：
Miu[1]=1;//Miu(1)=1
for(int i=2;i<=m;i++){
if(!vis[i]) Prime[++cnt]=i,Miu[i]=-1;
for(int j=1,x;j<=cnt&&(x=i*Prime[j])<=m;j++){
vis[x]=1;
if(i%Prime[j]==0){
Miu[x]=0;
//x含有平方因子 Prime[j]*Prime[j],Miu(x)=0
break;
}
Miu[x]=-Miu[i];
//x=i*Prime[j],多乘了一个不同的质数,所以Miu(x)=Miu(i)*-1
}
}
莫比乌斯函数的精髓是以下结论：
\[f(n)=\sum\limits_{d|n}\mu(d),f(n)=[n=1] \]-
证明：
随便手推一下就可以得到 \(f(1)=1\)。
如果 \(d\) 含有平方因子，根据定义有 \(\mu(d)=0\)，对答案没有贡献。因此，\(n\) 中所含的平方因子也是没有意义的。所以若 \(n=\prod\limits_{i=1}^{k}p_i^{q_i},n'=\prod\limits_{i=1}^{k}p_i\)，有 \(f(n)=f(n')\)（\(n\) 比 \(n'\) 多的因子都是平方因子）。
考虑证明对于 \(n=\prod\limits_{i=1}^{k}p_i(n\not=1)\)，\(f(n)=0\)。
根据约数个数定理，\(n\) 的因子有 \(2^k\) 个。因为 \(n\not=1\)，有 \(k \ge 1\)，所以在 \(n\) 的因子中，有 \(2^{k-1}\) 个因子是 偶数个不同的质因数的乘积（即 \(\mu(x)=1\)），\(2^{k-1}\) 个因子是 奇数个不同的质因数的乘积（即 \(\mu(x)=-1\)）。两两抵消，\(f(n)=0\)。
证毕。
至于那个莫比乌斯反演的经典式子，本质上就是 \(\sum\limits_{d|n}\mu(d)=[n=1]\) 的推论罢了。
应用莫比乌斯反演本质上是利用 \(\mu\) 函数的性质，通过凑出 形如 \([n=1]\) 的项来对式子进行转化，然后再通过改变枚举顺序、设参等方法将其变为可以用其他算法快速求解的式子（如线性筛，整除分块，杜教筛等）。
注意，题目一般运用的转换是 \([n=1]=\sum\limits_{d|n}\mu(d)\)，而不是 \(\sum\limits_{d|n}\mu(d)=[n=1]\)。
[HAOI2011]Problem b题目大意：
给定 \(a,b,c,d,k\)，求 \(\sum\limits_{i=a}^b\sum\limits_{j=c}^d[gcd(i,j)=k]\)。
先转换为 \(\sum\limits_{i=1}^b\sum\limits_{j=1}^d[gcd(i,j)=k]\)，推就完事了（最后容斥计算答案即可）。
\[\sum\limits_{i=1}^b\sum\limits_{j=1}^d[gcd(i,j)=k] \]\[=\sum\limits_{i=1}^{\lfloor \frac{b}{k}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{d}{k}\rfloor}[gcd(i,j)=1] \]通过转换，我们凑出了 \([n=1]\) 的形式。带入 \(\mu\) 函数：
\[=\sum\limits_{i=1}^{\lfloor \frac{b}{k}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{d}{k}\rfloor}\sum\limits_{d|gcd(i,j)}\mu(d) \]先枚举 \(gcd(i,j)\)：
\[=\sum\limits_{g=1}^{min(b,d)}\mu(g)\sum\limits_{g|i}^{b}\sum\limits_{j|g}^{d}1 \]\[=\sum\limits_{g=1}^{min(b,d)}\mu(g)\lfloor{\frac{b}{j}}\rfloor\lfloor{\frac{d}{j}}\rfloor \]线性筛出 \(\mu\) 函数，维护前缀和后用值域分块求解即可。时间复杂度 \(O(\sqrt b+\sqrt d+\max(b,d))\)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=50010;
inline int read(){
int x=0;
char c=getchar();
for(;!(c>='0'&&c<='9');c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+c-'0';
return x;
}
bool vis[maxn];
int Prime[maxn],cnt;
int Miu[maxn],n,k;
void Init(int n){
Miu[1]=1;//线性筛
for(int i=2;i<=n;i++){
if(!vis[i]){
Prime[++cnt]=i;
Miu[i]=-1;
}
for(int j=1,x;j<=cnt&&(x=i*Prime[j])<=n;j++){
vis[x]=1,Miu[x]=-Miu[i];
if(i%Prime[j]==0){
Miu[x]=0;
break;
}
}
}
for(int i=1;i<=n;i++) Miu[i]+=Miu[i-1];
}
ll Query(int n,int m,ll sum=0){
//整除分块
for(int l=1,r=1;l<=min(n/k,m/k);l=r+1){
r=min(n/(n/l),m/(m/l));
sum+=(ll)(Miu[r]-Miu[l-1])*(n/(k*l))*(m/(k*l));
}
return sum;
}
int main(){
n=read();
Init(5e4);
int a,b,c,d;
while(n--){
a=read(),b=read(),c=read(),d=read(),k=read();
printf("%lld\n",Query(b,d)-Query(a-1,d)-Query(b,c-1)+Query(a-1,c-1));
}
return 0;
}
题目大意：
\[\sum\limits_{i=1}^n\sum\limits_{j=1}^m lcm(i,j) \]\[=\sum\limits_{i=1}^n\sum\limits_{j=1}^m \frac{ij}{gcd(i,j)} \]给定 \(n,m\)，求 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^m lcm(i,j)\) 对 \(20101009\) 取模的结果。
先枚举 \(gcd(i,j)\)：
\[=\sum\limits_{k=1}^{min(n,m)}\sum\limits_{i=1}^n\sum\limits_{j=1}^m \frac{ij}{k}\times[gcd(i,j)=k] \]\[=\sum\limits_{k=1}^{min(n,m)}\frac{1}{k}\sum\limits_{i=1}^ni\sum\limits_{j=1}^mj \times[gcd(i,j)=k] \]\[=\sum\limits_{k=1}^{min(n,m)}\frac{1}{k}\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}ki\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}kj \times[gcd(i,j)=1] \]\[=\sum\limits_{k=1}^{min(n,m)}k\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}i\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}j \times[gcd(i,j)=1] \]再次凑出了形如 \([n=1]\) 的式子，带入 \(\mu\) 函数：
\[=\sum\limits_{k=1}^{min(n,m)}k\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}i\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}j \sum\limits_{d|gcd(i,j)}\mu(d) \]先枚举 \(d\)：
\[=\sum\limits_{d=1}^{min(n,m)}\mu(d)\sum\limits_{k=1}^{min(n,m)}k\sum\limits_{d|i}^{\lfloor\frac{n}{dk}\rfloor}i\sum\limits_{d|j}^{\lfloor\frac{m}{k}\rfloor}j \]\[=\sum\limits_{d=1}^{min(n,m)}\mu(d)\sum\limits_{k=1}^{min(n,m)}k\sum\limits_{i=1}^{\lfloor\frac{n}{dk}\rfloor}di\sum\limits_{j=1}^{\lfloor\frac{m}{dk}\rfloor}dj \]\[=\sum\limits_{d=1}^{min(n,m)}d^2\mu(d)\sum\limits_{k=1}^{min(n,m)}k\sum\limits_{i=1}^{\lfloor\frac{n}{dk}\rfloor}i\sum\limits_{j=1}^{\lfloor\frac{m}{dk}\rfloor}j \]\[=\sum\limits_{d=1}^{min(n,m)}d^2\mu(d)\sum\limits_{k=1}^{min(n,m)}k\frac{\lfloor\frac{n}{dk}\rfloor(\lfloor\frac{n}{dk}\rfloor+1)}{2}\frac{\lfloor\frac{m}{dk}\rfloor(\lfloor\frac{m}{dk}\rfloor+1)}{2} \]\[=\sum\limits_{d=1}^{min(n,m)}d^2\mu(d)\sum\limits_{k=1}^{min(n,m)}k\frac{\lfloor\frac{n}{dk}\rfloor\lfloor\frac{m}{dk}\rfloor(\lfloor\frac{n}{dk}\rfloor+1)(\lfloor\frac{m}{dk}\rfloor+1)}{4} \]考虑先枚举 \(t=dk\)：
\[=\sum\limits_{t=1}^{min(n,m)}\frac{\lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor(\lfloor\frac{n}{t}\rfloor+1)(\lfloor\frac{m}{t}\rfloor+1)}{4}\sum\limits_{d|t}d^2\mu(d)\frac{t}{d} \]\[=\sum\limits_{t=1}^{min(n,m)}t\frac{\lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor(\lfloor\frac{n}{t}\rfloor+1)(\lfloor\frac{m}{t}\rfloor+1)}{4}\sum\limits_{d|t}d\mu(d) \]设 \(F(n)=\sum\limits_{d|n}d\mu(d)\)：
\[=\sum\limits_{t=1}^{min(n,m)}\frac{\lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor(\lfloor\frac{n}{t}\rfloor+1)(\lfloor\frac{m}{t}\rfloor+1)}{4}tF(t) \]线性筛出 \(F\) 后用整除分块即可。时间复杂度 \(O(\sqrt{n}+\sqrt{m}+\max(n,m))\)。
#include<bits/stdc++.h>
using namespace std;
const int maxn=10000010;
const int mod=20101009;
bool vis[maxn];
int n,m,Prime[maxn],f[maxn],g[maxn],cnt;
int fastpow(int n,int m){
int a=n,S=1;
while(m){
if(m&1) S=S*1ll*a%mod;
a=a*1ll*a%mod,m>>=1;
}
return S;
}
int Divid(int a,int b){return fastpow(b,mod-2)*1ll*a%mod;}
void init(int N=max(n,m)){
int tmp,c;//线性筛
f[1]=1,g[0]=1;
for(int i=2;i<=N;i++){
if(!vis[i])
Prime[++cnt]=i,f[i]=mod-i+1;
for(int j=1,x;j<=cnt&&Prime[j]*1ll*i<=N;j++){
vis[x=Prime[j]*i]=1;
if(i%Prime[j]==0){
f[x]=f[i];
break;
}
f[x]=(f[i]-f[i]*1ll*Prime[j]%mod+mod)%mod;
}
}
for(int i=1;i<=N;g[i]=g[i-1]*1ll*i%mod,i++)
f[i]=(Divid(f[i],4)*1ll*i%mod+f[i-1])%mod;
}
int Query(int sum=0){
int tmp;.//整除分块
for(int l=1,r=1;l<=min(n,m);l=r+1){
r=min(n/(n/l),m/(m/l));
tmp=((n/l)*(n/l+1ll)%mod)*((m/l)*(m/l+1ll)%mod)%mod;
tmp=tmp*1ll*(f[r]-f[l-1]+mod)%mod;
if((sum+=tmp)>=mod) sum-=mod;
}
return sum;
}
int main(){
scanf("%d%d",&n,&m),init();
printf("%d\n",Query());
return 0;
}