莫比乌斯反演

莫比乌斯反演例题

原理：

\[f(x)=\sum_{d\mid x} g(d) \iff g(x)=\sum_{d\mid x} \mu(d)f(\dfrac x d) \]

\[f(x)=\sum_{x\mid d} g(d) \iff \sum_{x\mid d}\mu(\dfrac d x) f(d) \]

技巧：

\[[\gcd (x,y)=1]=\sum_{d\mid \gcd(x,y)} \mu(d) \]

\[\sum _{d\mid n} \mu(d) = [n=1] \]

\[d(i\times j) =\sum_{x\mid i} \sum _{y\mid j}[\gcd(x,y)==1] \]

对于这种与 $\gcd$ 相关的莫比乌斯反演，一般我们都是套路的去设 $f(d)$ 为 $\gcd (i,j)=d$ 的个数，$g(n)$ 为 $\gcd (i,j)=n$ 和 $n$ 的倍数的数的个数

即：

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

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

由定义我们容易发现：$f(x)$ 和 $g(x)$ 是有某些关联的，那么我们尝试去发现 $f(x)$ 和 $g(x)$ 的关系，可以发现：

\[g(x)=\sum_{x\mid d} f(d)=\lfloor \dfrac n x \rfloor \lfloor \dfrac m x \rfloor \]

那么此时我们显然就可以运用反演了：

\[g(x)=\sum_{x\mid d} f(d)=\lfloor \dfrac n x \rfloor \lfloor \dfrac m x \rfloor\iff f(x)=\sum_{d\mid x} \mu(d)g(\dfrac x d) \]

典型例题

P3455 [POI2007]ZAP-Queries

题目描述：

求解：

\[\sum _{i=1}^a \sum _{j=1 }^b [\gcd (i,j)==k] \]

那么我们设

\[f(k)=\sum_{i=1}^a \sum_{j=1}^b [\gcd(i,j)=k] \]

\[F(n)=\sum_{n\mid k} f(k)=\lfloor \dfrac a n \rfloor \lfloor \dfrac b n \rfloor \]

由反演可知：

\[f(n)=\sum_{n\mid k} \mu(\lfloor \dfrac k n \rfloor)F(k) \]

我们要求的答案应该是 $f(k)$

那么我们有：

\[f(k)=\sum _{k\mid d} \mu(\lfloor \dfrac d k \rfloor)F(d) \]

把 $F(d)$ 化简可得：

\[f(k)=\sum _{k\mid d} \mu(\lfloor \dfrac d k \rfloor)\lfloor \dfrac a d \rfloor \lfloor \dfrac b d \rfloor \]

设 $\lfloor \dfrac d k\rfloor$ 为 $t$

则 $d=kt$ ，所以：

\[f(k)=\sum _{t=1} ^{\min(a,b)} \mu (t)\lfloor \dfrac a {kt} \rfloor \lfloor \dfrac b {kt} \rfloor \]

我们根据这个就可以利用整数分块来求了

P2257 YY的GCD

题目描述：

\[\sum _{i=1} ^n \sum_{j=1}^m [\gcd (i,j)==k]~~{k\in prime} \]

首先我们还是先化简原式：

设：

\[f(x)=\sum _{i=1} ^n \sum_{j=1}^m [\gcd (i,j)==x]\\ F(x)=\sum _{x\mid d} f(d)=\lfloor \dfrac n x \rfloor \lfloor \dfrac m x \rfloor\\ f(x)=\sum_{x\mid d} \mu(\lfloor\dfrac d x \rfloor) F(d) \]

然后我们把题目写成一般形式就是：

\[\sum_{p\in prime}\sum _{i=1}^n \sum _{j=1}^m[\gcd(i,j)==p] \]

我们要求的答案就是：

\[\sum_{p\in prime}f(p) \]

我们利用莫比乌斯反演，即上面的第三个式子就有：

\[\sum_{p\in prime} f(p) =\sum_{p\in prime} \sum_{p\mid d} \mu(\lfloor\dfrac d p \rfloor) F(d) \]

我们设 $\lfloor \dfrac d p\rfloor = t$ 则 $d=pt$

\[\sum_{p\in prime} f(p) =\sum_{p\in prime} \sum_{t=1}^{\min(\lfloor \frac n {p} \rfloor,\lfloor \frac m {p} \rfloor)} \mu(t) F(pt) =\sum_{p\in prime} \sum_{t=1}^{\min(\lfloor \frac n {p} \rfloor,\lfloor \frac m {p} \rfloor)} \mu(t) \lfloor \dfrac n {pt} \rfloor \lfloor \dfrac m {pt} \rfloor \]

现在我们是枚举每一个 $p$ 的倍数进行处理，因此我们也可以改成枚举每一个数的质因数

\[\sum_{i=1}^{\min (n,m)} \sum _{t\in prime ~\cap~ t\mid i} \mu(\dfrac i t)\lfloor \dfrac{m}{i} \rfloor \lfloor \dfrac{n}{i}\rfloor \]

把 $\lfloor \dfrac m i \rfloor \lfloor \dfrac n i\rfloor $ 扔出来就有：

\[\sum_{i=1}^{\min (n,m)} \lfloor \dfrac{m}{i} \rfloor \lfloor \dfrac{n}{i}\rfloor\sum _{t\in prime ~\cap~ t\mid i} \mu(\dfrac i t) \]

我们观察发现：后面的 $\sum \mu (\dfrac i t)$ 可以直接处理掉

当然，在我们也可以根据一些代数意义化简，当我们化简到这一步的时候：

\[\sum_{p\in prime} \sum_{p\mid d} \mu(\lfloor\dfrac d p \rfloor) F(d) \]

翻译成人话就是：对于每一个质数，我枚举它的倍数，使得 $ans$ 加上 $\mu(\lfloor\dfrac d p \rfloor) F(d)$

那么我们完全可以换一种思路，枚举每一个数，加上它分解质因数后的每一个因数即可，此时对于我的 $\mu$ 来说，就是 $i$ 是 $p$ 的多少倍，$F$ 就是当前的 $i$ 是几

\[\sum_{i=1}^{\min(n,m)} \sum _{p\in prime \cap p\mid i} \mu(\lfloor \dfrac i p \rfloor)F(i) \]

然后拆开 $F(i)$ 就行了

\[\sum_{i=1}^{\min (n,m)} \sum _{p\in prime ~\cap~ p\mid i} \mu(\lfloor \dfrac i p \rfloor)\lfloor \dfrac{m}{i} \rfloor \lfloor \dfrac{n}{i}\rfloor \\ \sum_{i=1}^{\min (n,m)} \lfloor \dfrac{m}{i} \rfloor \lfloor \dfrac{n}{i}\rfloor\sum _{p\in prime ~\cap~ p\mid i} \mu(\lfloor \dfrac i p \rfloor) \]

其实和上面的化简是长的一样的，只是换一种理解方式，可以减少很多不必要的步骤。

/*
BlackPink is the Revolution
light up the sky
Blackpink in your area
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define int long long
using namespace std;
const int N=1e7+5e5+5;
const int mod=1e9+7;
const double pi=3.141592653589793;
typedef long long ll;
typedef pair P;
namespace scan{
    template 
    void read(T &x){
        x=0; char c=getchar(); int f=0;
        for(; !isdigit(c); c=getchar()) f |= c=='-';
        for(; isdigit(c); c=getchar()) x = x*10+(c^48);
        if(f) x = -x;
    }

    template 
    void write(T &x,char ch){
        if(x<0) putchar('-'), x = -x;
        static short st[30],tp;
        do st[++tp] = x%10, x/=10; while(x);
        while(tp) putchar(st[tp--] | 48);
        putchar(ch);
    }
}
using namespace scan;
int n,m,cnt;
int prime[N],mu[N],g[N];
int sum[N];
bool st[N];
inline void get_prime(int n){
	mu[1]=1;
	for(int i=2;i



P3327 [SDOI2015]约数个数和
题目描述：
\[\sum_{i=1}^n \sum _{j=1} ^m d(i\times j)
\]

首先有一个引理：
\[d(i\times j) =\sum _{a \mid i} \sum _{b\mid j} [\gcd(a,b)==1]
\]
找了半天也没找到证明，貌似只有一个，还是我没看懂的

所以我们就直接搞吧
\[\begin{align*}
\sum_{i=1}^n \sum _{j=1} ^m d(i\times j)&=\sum_{i=1}^n \sum _{j=1}^m\sum _{a \mid i} \sum _{b\mid j} [\gcd(a,b)==1]\\
&=\sum _{a=1} \sum_{b=1} \lfloor \dfrac n a \rfloor \lfloor \dfrac m b \rfloor [\gcd(a,b)==1]
\end{align*}
\]
于是我们直接设
\[f(x)=\sum _{i=1} \sum_{j=1} \lfloor \dfrac n i \rfloor \lfloor \dfrac m j \rfloor [\gcd(i,j)==1]\\
F(x)=\sum_{x\mid d}f(d)
\]
反演一下：
\[f(x)=\sum_{x\mid d} \mu(\lfloor\dfrac d x \rfloor) F(d)
\]
于是有：
\[\begin{align*}
F(x)&=\sum _{i=1}^n \sum_{j=1}^m \lfloor \dfrac n i \rfloor \lfloor \dfrac m j \rfloor [ x|\gcd(i,j)]\\
&=\sum_{i=1}^{\frac n x} \sum_{j=1}^{\frac m x}\lfloor \dfrac n {xi}\rfloor \lfloor \dfrac {m}{xj}\rfloor
\end{align*}
\]
我们的答案是 \(f(1)\)
所以
\[f(1)=\sum _{d=1}^n \mu (d)F(d)\\
f(1)=\sum _{d=1}^n \mu (d)\sum_{i=1}^{\frac n d} \sum_{j=1}^{\frac m d}\lfloor \dfrac n {di}\rfloor \lfloor \dfrac {m}{dj}\rfloor
\]
我们发现前面的 \(\mu\) 可以前缀和预处理掉显然好处理，后面的我们可以考虑想想办法
我们尝试先把后面的 \(d\) 扔出去
\[f(1)=\sum _{d=1}^n \mu (d)\sum_{i=1}^{\frac n d} \sum_{j=1}^{\frac m d}\lfloor \dfrac n {di}\rfloor \lfloor \dfrac {m}{dj}\rfloor
\]
我们这时候发现 \(\lfloor \dfrac n {di} \rfloor\) 与 \(j\) 无关，可以放到前面：
\[f(1)=\sum _{d=1}^n \mu (d)\sum_{i=1}^{\frac n d} \lfloor \dfrac n {di}\rfloor \sum_{j=1}^{\frac m d} \lfloor \dfrac {m}{dj}\rfloor
\]
我们发现后面的两个 \(\Sigma\) 互不影响
这样，我们就可以分别处理了，时间复杂度 \(O(T\sqrt n +n\sqrt n)\)
/*
BlackPink is the Revolution
light up the sky
Blackpink in your area
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
using ll=long long;
const int N=5e4+5;
const int mod=1e9+7;
const double pi=3.141592653589793;
typedef long long ll;
typedef pair P;

namespace scan{
    template 
    void read(T &x){
        x=0; char c=getchar(); int f=0;
        for(; !isdigit(c); c=getchar()) f |= c=='-';
        for(; isdigit(c); c=getchar()) x = x*10+(c^48);
        if(f) x = -x;
    }

    template 
    void write(T x,char ch){
        if(x<0) putchar('-'), x = -x;
        static short st[30],tp;
        do st[++tp] = x%10, x/=10; while(x);
        while(tp) putchar(st[tp--] | 48);
        putchar(ch);
    }
}
using namespace scan;
int n,m,T;
int mu[N];
long long sum[N],h[N];
inline void get_mu(int n){
	mu[1]=1;
	for(int i=1;i<=n;i++)
		for(int j=i+i;j<=n;j+=i) mu[j]-=mu[i];
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+mu[i];
	for(int d=1;d<=n;d++){
		ll res=0;
		for(int l=1,r;l<=d;l=r+1){
			r=d/(d/l);
			res+=1ll*(r-l+1)*1ll*(d/l);
		}
		h[d]=res;
	}//n sqrt n
}
int main(){
    get_mu(N-5);
    // for(int i=1;i<=100;i++) cout<m) swap(n,m);
    	ll ans=0;
    	for(int l=1,r;l<=n;l=r+1){
    		r=min(n/(n/l),m/(m/l));
    		// cout<


P1829 [国家集训队]Crash的数字表格 / JZPTAB
题目描述：
\[\sum _{i=1}^n \sum _{j=1} ^m \mathrm{lcm}(i,j)
\]
数据范围：\(1\le n,m\le 10^7\)

首先我们根据小学知识可以发现
\(\gcd(i,j)*\mathrm{lcm}(i,j)=i\times j\)
所以我们的题意就变成了
\[\sum _{i=1}^n \sum _{j=1} ^m \dfrac {ij}{\gcd(i,j)}
\]
那么就好做多了，我们可以直接枚举 $\gcd $ 并把它放到最前面
\[\sum_{d=1}^{\min(n,m)}\sum_{i=1}^ n \sum_{j=1}^m [gcd (i,j)==d]\dfrac {ij} {d}\\
\]
我们枚举 \(d\) 的倍数可以发现：
\[\sum_{d=1}^{\min(n,m)}\sum_{i=1}^{\frac n d}\sum_{j=1}^{\frac m d} i j d [\gcd(i,j)=1]\\
\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{\frac n d}\sum_{j=1}^{\frac m d} i j[\gcd(i,j)=1]\\
\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{\frac n d}i\sum_{j=1}^{\frac m d} j\sum_{k\mid \gcd(i,j)} \mu(k)\\
\]
我们把 \(\mu (k)\)  的枚举项拿出来，那么式子就变成了（为了方便，就不写 \(\min\) 了）
\[\sum_{d=1} ^n d\sum_{k=1}^n\mu(k) \sum_{k\mid i}^{\frac n d} i\sum_{k\mid j}^{\frac m d}j\\
\]
我们这个式子的最后一个 \(\sum\) 的意思是，从 \(1\sim \dfrac n d\) 中选取 \(k\) 的倍数相加，那么我们可以直接写成：
\[\sum_{d=1} ^n d\sum_{k=1}^n\mu(k) \sum_{i=1}^{\frac n {dk}} ik\sum_{j=1}^{\frac m {dk}}jk\\
\sum_{d=1} ^n d\sum_{k=1}^n k^2 \mu(k) \sum_{i=1}^{\frac n {dk}} i\sum_{j=1}^{\frac m {dk}}j\\
\]
最后两个 \(\sum\) 很明显示两个等差数列，我们兴奋地写成等差数列形式
\[\sum_{d=1} ^n d\sum_{k=1}^nk^2\mu(k)\dfrac {\lfloor \frac n {dk} \rfloor(\lfloor \frac n {dk} \rfloor+1)} {2}\dfrac {\lfloor \frac m {dk} \rfloor(\lfloor \frac m {dk} \rfloor+1)} 2
\]
然后我们先枚举后面巨大的等差数列求和就有：
\[\sum_{d=1} ^n\sum_{k=1}^ndk^2\mu(k)\dfrac {\lfloor \frac n {dk} \rfloor(\lfloor \frac n {dk} \rfloor+1)} {2}\dfrac {\lfloor \frac m {dk} \rfloor(\lfloor \frac m {dk} \rfloor+1)} 2
\]
那么后面就可以分别预处理加整除分块来做了！
/*
BlackPink is the Revolution
light up the sky
Blackpink in your area
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
using ll=long long;
const int N=1e7+5;
const int mod=20101009;
const double pi=3.141592653589793;
typedef pair P;

namespace scan{
    template 
    void read(T &x){
        x=0; char c=getchar(); int f=0;
        for(; !isdigit(c); c=getchar()) f |= c=='-';
        for(; isdigit(c); c=getchar()) x = x*10+(c^48);
        if(f) x = -x;
    }

    template 
    void write(T x,char ch){
        if(x<0) putchar('-'), x = -x;
        static short st[30],tp;
        do st[++tp] = x%10, x/=10; while(x);
        while(tp) putchar(st[tp--] | 48);
        putchar(ch);
    }
}
using namespace scan;
int mu[N],prime[N],cnt;
ll sum[N],h[N];
bool st[N];
template
inline int qm(T a){
	return (a%mod+mod)%mod;
}

inline int add(int a,int b){
	return (a+b)%mod;
}

inline void get_prime(int n){
	mu[1]=1;
	for(int i=2;iy) swap(x,y);
	ll res=0;
	for(int l=1,r;l<=x;l=r+1){
		r=min(x/(x/l),y/(y/l));
		res=add(res, qm(1ll*(sum[r]-sum[l-1])*(get_sum(x/l,y/l))));
	}
	return res%mod;
}

int n,m;
ll res=0;
int main(){
	get_prime(N);
    read(n),read(m);
    if(n>m) swap(n,m);
    for(int l=1,r;l<=n;l=r+1){
    	r=min(n/(n/l), m/(m/l));
    	res=add(res, qm(1ll*(r-l+1)*(l+r)/2%mod*g(n/l,m/l)));
    }
    write(qm(res),'\n');
    return 0;
}


AT5200 [AGC038C] LCMs
题目描述：
\[\sum_{i=1}^n \sum_{j=i+1}^m \mathrm{lcm}(A_i,A_j)
\]

首先，利用容斥原理我们会发现，上面的这个玩意长成这样肯定不想要的
于是我们把它们放到一个按 \(A_1 ~A_2~A_3~A_4~A_5~A_6\dots A_n\) 上

很容易发现，我们要求的就是右边的那个大三角，
但是我们发现肯定是左边的更好处理，所以我们可以开始行动了
\[\sum_{i=1}^n \sum_{j=i+1}^m \mathrm{lcm}(A_i,A_j)=\dfrac {\sum_{i=1}^n \sum_{j=1}^m \mathrm{lcm}(i,j)-\sum_{i=1}^n A_i} 2
\]
那我们就只把那一块拿出来观察：
\[\begin{align*}
\sum_{i=1}^n \sum_{j=1}^m \mathrm{lcm}(A_i,A_j)&=\sum_{i=1}^n \sum_{j=1}^m \dfrac {A_iA_j} {\gcd(A_i,A_j)}\\
&=\sum_{d=1}^{\max{A}}\dfrac 1 d\sum_{i=1}^n\sum_{j=1}^n [\gcd(A_i,A_j)==d]A_iA_j\\
&=\sum_{d=1}^{\max{A}}\dfrac 1 d\sum_{i=1}^n\sum_{j=1}^n A_iA_j[d\mid A_i][d\mid A_j][\gcd(\dfrac {A_i} {d} ,\dfrac {A_j} {d})==1]\\
\end{align*}
\]
然后我们就能进行反演了：
\[\sum_{d=1}^{\max{A}}\dfrac 1 d\sum_{i=1}^n\sum_{j=1}^n A_iA_j[d\mid A_i][d\mid A_j][\gcd(\dfrac {A_i} {d} ,\dfrac {A_j} {d})==1]\\
\sum_{d=1}^{\max{A}}\dfrac 1 d\sum_{i=1}^n\sum_{j=1}^n A_iA_j[d\mid A_i][d\mid A_j]\sum_{k\mid \gcd(\frac {A_i} {d} ,\frac {A_j} {d})} \mu(k)\\
\sum_{d=1}^{\max{A}}\sum_{k=1}^{\frac {\max A} d}\dfrac {\mu(k)} d\sum_{i=1}^n\sum_{j=1}^n A_iA_j[dk\mid A_i][dk\mid A_j]\\
\sum_{d=1}^{\max{A}}\sum_{k=1}^{\frac {\max A} d}\dfrac {\mu(k)} d(\sum_{i=1}^nA_i[dk\mid A_i])^2\\
\]
后面的应该可以开个桶来处理了
然后我们直接枚举桶里面的元素即可