c/c++语言开发共享莫比乌斯反演小记

写在前面

这是蒟蒻第一次写这么长的博文

(gyh nb)，(text{oi-wiki} nb)

如果觉得写得凑合就点个支持吧(qwq)

前置知识

、、(有空慢慢补)

mobius函数

定义

莫比乌斯函数(mu(n))定义为：

其中(p_1p_2…，p_s)是不同素数。

可以看出，当(n)没有平方因子时，(mu(n))非零。

(mu)也是积性函数。

性质

莫比乌斯函数具有如下的性质：

使用狄利克雷卷积来表示，即

证明：

(n=1)时显然成立。

若(n>1)，设(n)有(s)个不同的素因子，由于(mu(d)neq0)当且仅当(d)无平方因子，故(d)中每个素因子的指数只能为(0)或(1)。

若(n)的某个因子(d)，有(mu(d)=(-1)^i)，则它由(i)个本质不同的质因子构成。因为质因子的总数为(s)，所以满足上式的因子数有(c_s^i)个。

所以我们就可以对于原式，转化为枚举(mu(d))的值，同时运用二项式定理，故有

该式在(s=0)即(n=1)时为1，否则为(0)。

求莫比乌斯函数

因为莫比乌斯函数是积性函数，所以可以用线性筛

int n, cnt, p[a], mu[a]; bool vis[a];  void getmu() {     mu[1] = 1;     for (int i = 2; i <= n; i++) { 	if (!vis[i]) mu[i] = -1, p[++cnt] = i; 	for (int j = 1; j <= cnt && i * p[j] <= n; j++) { 	    vis[i * p[j]] = 1; 	    if (i % p[j] == 0) { mu[i * p[j]] = 0; break; } 	    mu[i * p[j]] -= mu[i]; 	}     } } 

莫比乌斯反演公式

设(f(n))，(g(n))为两个数论函数。

如果有

则有

证明

• 法一：对原式做数论变换

  1. (sumlimits_{d|n}g(d))替换(f(n))，即

     [sumlimits_{d|n}mu(d)f(frac{n}{d})=sumlimits_{d|n}mu(d)sumlimits_{k|frac nd}g(k) ]

  2. 变换求和顺序得

     [sumlimits_{k|n}g(k)sumlimits_{d|frac n k}mu(frac nk) ]

  3. 因为(sumlimits_{d|n}mu(d)=[n=1])，所以只有在(frac{n}{k}=1)即(n=k)时才会成立，所以上式等价于

     [sumlimits_{d|n}[n=k]g(k)=g(n) ]

  得证

• 法二：利用卷积

  原问题为：已知(f=g*1)，证明(g=f*mu)

  转化：(f*mu=g*1*mu=g*varepsilon=g)（(1*mu=varepsilon)）

  再次得证= =

小性质

([gcd(i,j)=1]leftrightarrowsumlimits_{d|gcd(i,j)}mu(d))

证明

• 法一：

  设(n=gcd(i,j))，那么等式右边(=sumlimits_{d|n}mu(d)=[n=1]=[gcd(i,j)=1]=)等式左边

• 法二：

  利用单位函数暴力拆开：([gcd(i,j)=1]=varepsilon(gcd(i,j))=sumlimits_{d|gcd(i,j)}mu(d))

做题思路&&应用

利用狄利克雷卷积可以解决一系列求和问题。常见做法是使用一个狄利克雷卷积替换求和式中的一部分，然后调换求和顺序，最终降低时间复杂度。

经常利用的卷积有(mu*1=epsilon)和(text{id}=varphi*1)。

题

还是以题为主吧，但是做的题也会单独写题解，毕竟要多水几篇博客的嘛/huaji

洛谷 p2522 [haoi2011]problem b

题目链接

有(n)组询问，每次给出(a,b,c,d,k)，求(sumlimits_{x=a}^{b}sumlimits_{y=c}^{d}[gcd(x,y)=k])

设(f(n,m)=sumlimits_{i=1}^{n}sumlimits_{j= 1}^{m}[gcd(i,j)=k])

那么根据容斥原理，题目中的式子就转化成了(f(b,d)-f(b, c – 1) – f(a – 1,d) + f(a – 1, c – 1))

所以我们接下来的问题就转化为了如何求(f)的值

现在来化简(f)的值

1. 容易得出原式等价于$$sumlimits_{i = 1}^{lfloorfrac{n}{k}rfloor}sumlimits_{j = 1}^{lfloorfrac{m}{k}rfloor}[gcd(i,j) = 1]$$

2. 因为(epsilon(n) =sumlimits_{d|n}mu(d)=[n=1])，由此可将原式化为

   [sumlimits_{i=1}^{lfloorfrac{n}{k}rfloor}sumlimits_{j=1}^{lfloorfrac{m}{k}rfloor}sumlimits_{d|gcd(i,j)}mu(d) ]

3. 改变枚举对象并改变枚举顺序，先枚举(d)，得

   [sumlimits_{d=1}^{min(n,m)}mu(d)sumlimits_{i=1}^{lfloorfrac{n}{k}rfloor}[d|i]sumlimits_{j=1}^{lfloorfrac{m}{k}rfloor}[d|j] ]

   也就是说当(d|i)且(d|j)时，(d|gcd(i,j))

4. 易得(1sim lfloorfrac{n}{k}rfloor)中一共有(lfloorfrac{n}{dk}rfloor)个(d)的倍数，同理(1sim lfloorfrac{m}{k}rfloor)中一共有(lfloorfrac{m}{dk}rfloor)个(d)的倍数，于是原式化为$$sumlimits_{d=1}^{min(n,m)}mu(d)lfloorfrac{n}{dk}rfloorlfloorfrac{m}{dk}rfloor$$

此时已经可以(o(n))求解，但是过不了，因为有很多值相同的区间，所以可以用数论分块来做

先预处理(mu)，再用数论分块，复杂度(o(n+tsqrt n))

我的代码每次得分玄学，看评测机心情，建议自己写

/* author:loceaner */ #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std;  const int a = 1e6 + 11; const int b = 1e6 + 11; const int mod = 1e9 + 7; const int inf = 0x3f3f3f3f;  inline int read() { 	char c = getchar(); int x = 0, f = 1; 	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1; 	for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48); 	return x * f; }  int n, a, b, c, d, k, cnt, p[a], mu[a], sum[a]; bool vis[a];  void getmu() { 	int max = 50010; 	mu[1] = 1; 	for (int i = 2; i <= max; i++) { 		if (!vis[i]) mu[i] = -1, p[++cnt] = i; 		for (int j = 1; j <= cnt && i * p[j] <= max; j++) { 			vis[i * p[j]] = true; 			if (i % p[j] == 0) break; 			mu[i * p[j]] -= mu[i]; 		} 	} 	for (int i = 1; i <= max; i++) sum[i] = sum[i - 1] + mu[i]; }  int work(int x, int y) { 	int ans = 0ll; 	int max = min(x, y); 	for (int l = 1, r; l <= max; l = r + 1) { 		r = min(x / (x / l), y / (y / l)); 		ans += (1ll * x / (l * k)) * (1ll * y / (l * k)) * 1ll * (sum[r] - sum[l - 1]);  	} 	return ans; }  void solve() { 	a = read(), b = read(), c = read(), d = read(), k = read(); 	cout << work(b, d) - work(a - 1, d) - work(b, c - 1) + work(a - 1, c - 1) << 'n'; }  signed main() { 	getmu(); 	int t = read(); 	while (t--) solve(); 	return 0; } 

洛谷 p3455 [poi2007]zap-queries

题目链接

有(t)组询问，每次询问求

因为我不喜欢用(x、y、a、b、d)，所以一一对应换成(i、j、n、m、k)

直接淦式子

现在就可以每次询问(o(n))做这道题了

但是跑不过啊，不过显然可以数论分块，所以我们就可以(o(sqrt n))回答每次询问了

/* author:loceaner */ #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std;  const int a = 5e5 + 11; const int b = 1e6 + 11; const int mod = 1e9 + 7; const int inf = 0x3f3f3f3f;  inline int read() { 	char c = getchar(); int x = 0, f = 1; 	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1; 	for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48); 	return x * f; }  int n, m, k, mu[a], p[a], sum[a], cnt; bool vis[a];  void getmu(int n) { 	mu[1] = 1; 	for (int i = 2; i <= n; i++) { 		if (!vis[i]) p[++cnt] = i, mu[i] = -1; 		for (int j = 1; j <= cnt && i * p[j] <= n; j++) { 			vis[i * p[j]] = 1; 			if (i % p[j] == 0) break; 			mu[i * p[j]] -= mu[i]; 		} 	} 	for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + mu[i]; }  int solve(int n, int m, int k) { 	int ans = 0, maxn = min(n, m); 	for (int l = 1, r; l <= maxn; l = r + 1) { 		r = min(n / (n / l), m / (m / l)); 		ans += (sum[r] - sum[l - 1]) * (n / (k * l)) * (m / (k * l)); 	} 	return ans; }  int main() { 	getmu(50000); 	int t = read(); 	while (t--) { 		n = read(), m = read(), k = read(); 		cout << solve(n, m, k) << 'n'; 	} 	return 0; } 

洛谷 p1829 [国家集训队]crash的数字表格 / jzptab

题目链接

求

容易想到原式等价于

枚举(i,j)的最大公约数(d)，显然(gcd(frac id,frac jd)=1)，即(frac id)和(frac jd)互质

变换求和顺序

记(sum(n,m)=sumlimits_{i=1}^{n}sumlimits_{j=1}^{m}[gcd(i,j)=1]i*j)

对其进行化简，用(varepsilon(gcd(i,j)))替换([gcd(i,j)=1])

转化为首先枚举约数

设(i=i’*d,j=j’*d)，则可以进一步转化

前半段可以处理前缀和，后半段可以(o(1))求，设

显然可以(o(1))求解

到现在

可以用数论分块求解

回带到原式中

又可以数论分块求解了

然后就做完啦

/* author:loceaner */ #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define int long long using namespace std;  const int a = 1e7 + 11; const int b = 1e6 + 11; const int mod = 20101009; const int inf = 0x3f3f3f3f;  inline int read() {     char c = getchar(); int x = 0, f = 1;     for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;     for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);     return x * f; }  bool vis[a]; int n, m, mu[a], p[b], sum[a], cnt;  void getmu() {     mu[1] = 1;     int k = min(n, m);     for (int i = 2; i <= k; i++) {         if (!vis[i]) p[++cnt] = i, mu[i] = -1;         for (int j = 1; j <= cnt && i * p[j] <= k; ++j) {             vis[i * p[j]] = 1;             if (i % p[j] == 0) break;             mu[i * p[j]] = -mu[i];         }     }     for (int i = 1; i <= k; i++) sum[i] = (sum[i - 1] + i * i % mod * mu[i]) % mod; }  int sum(int x, int y) {  	return (x * (x + 1) / 2 % mod) * (y * (y + 1) / 2 % mod) % mod;  }  int solve2(int x, int y) {     int res = 0;     for (int i = 1, j; i <= min(x, y); i = j + 1) {         j = min(x / (x / i), y / (y / i));         res = (res + 1ll * (sum[j] - sum[i - 1] + mod) * sum(x / i, y / i) % mod) % mod;     }     return res; }  int solve(int x, int y) {     int res = 0;     for (int i = 1, j; i <= min(x, y); i = j + 1) {         j = min(x / (x / i), y / (y / i));         res = (res + 1ll * (j - i + 1) * (i + j) / 2 % mod * solve2(x / i, y / i) % mod) % mod;     }     return res; }  signed main() {     n = read(), m = read();     getmu();     cout << solve(n, m) << 'n'; } 

洛谷 p2257 yy的gcd

题目链接

给定(n,m),求二元组((x,y))的个数，满足(1leq xleq n,1leq yleq m)，且(gcd(x,y))是素数。

(n,mleq 10^7)，自带多组数据，至多(10^{4})组数据。

思路与第一题problem b类似，在这里不再赘述，只给出代码= =

#include <cmath>  #include <cstdio> #include <cstring>  #include <iostream> using namespace std;  const int a = 1e7 + 11;   inline int read() { 	char c = getchar(); int x = 0, f = 1; 	for ( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;  	for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48); 	return x * f; }  bool vis[a]; long long sum[a]; int prim[a], mu[a], g[a], cnt, n, m;  void get_mu(int n) {     mu[1] = 1;     for (int i = 2; i <= n; i++) {         if (!vis[i]) {             mu[i] = -1;             prim[++cnt] = i;         }         for (int j = 1; j <= cnt && prim[j] * i <= n; j++) {             vis[i * prim[j]] = 1;             if (i % prim[j] == 0) break;             else mu[prim[j] * i] = - mu[i];         }     }     for (int j = 1; j <= cnt; j++)         for (int i = 1; i * prim[j] <= n; i++) g[i * prim[j]] += mu[i];     for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (long long)g[i]; }  signed main() {     int t = read();     get_mu(10000000);     while (t--) {         n = read(), m = read();         if (n > m) swap(n, m);         long long ans = 0;         for (int l = 1, r; 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 << ans << 'n';     }     return 0; } 

洛谷 p3327 [sdoi2015]约数个数和

题目链接

求

(d(x))为(x)的约数个数和

需要用到

证明我也不会

然后自己推导吧，在此不再赘述

/* author:loceaner */ #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std;  const int a = 5e5 + 11; const int b = 1e6 + 11; const int mod = 1e9 + 7; const int inf = 0x3f3f3f3f;  inline int read() { 	char c = getchar(); int x = 0, f = 1; 	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1; 	for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48); 	return x * f; }  bool vis[a]; int n, m, p[a], mu[a], cnt, sum[a]; long long g[a], ans;  void getmu(int n) { 	mu[1] = 1; 	for (int i = 2; i <= n; i++) { 		if (!vis[i]) mu[i] = -1, p[++cnt] = i; 		for (int j = 1; j <= cnt && i * p[j] <= n; j++) { 			vis[i * p[j]] = 1; 			if (i % p[j] == 0) break; 			mu[i * p[j]] -= mu[i]; 		} 	} 	for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + mu[i]; 	for (int i = 1; i <= n; i++) { 		int ans = 0; 		for (int l = 1, r; l <= i; l = r + 1) { 			r = (i / (i / l)); 			ans += 1ll * (r - l + 1) * (i / l); 		} 		g[i] = ans; 	} }  signed main() { 	int t = read(); 	getmu(50000); 	while (t--) { 		n = read(), m = read(); 		int maxn = min(n, m); 		ans = 0; 		for (int l = 1, r; l <= maxn; l = r + 1) { 			r = min(n / (n / l), m / (m / l)); 			ans += 1ll * (sum[r] - sum[l - 1]) * 1ll * g[n / l] * 1ll * g[m / l]; 		} 		cout << ans << 'n'; 	} 	return 0; } 

洛谷 p4449 于神之怒加强版

求

还是直接淦式子

令(p=dx)，则原式等于

显然前面的(lfloorfrac n{p}rfloorlfloorfrac m{p}rfloor)部分可以分块求解。

现在考虑后面的一部分，令

容易得出这个函数是积性函数，所以我们就可以线性筛然后求出其前缀和

然后就做完了

/* author:loceaner 莫比乌斯反演 */ #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define int long long using namespace std;  const int a = 5e6 + 11; const int b = 1e6 + 11; const int mod = 1e9 + 7; const int inf = 0x3f3f3f3f;  inline int read() { 	char c = getchar(); 	int x = 0, f = 1; 	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1; 	for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48); 	return x * f; }  bool vis[a]; int t, n, m, k, f[a], g[a], p[a], cnt, sum[a];  inline int power(int a, int b) { 	int res = 1; 	while (b) { 		if (b & 1) res = res * a % mod; 		a = a * a % mod, b >>= 1; 	} 	return res; }  inline int mo(int x) { 	if(x > mod) x -= mod; 	return x; }  inline void work() { 	g[1] = 1; 	int maxn = 5e6 + 1; 	for (int i = 2; i <= maxn; i++) { 		if (!vis[i]) { p[++cnt] = i, f[cnt] = power(i, k), g[i] = mo(f[cnt] - 1 + mod); } 		for (int j = 1; j <= cnt && i * p[j] <= maxn; j++) { 			vis[i * p[j]] = 1; 			if (i % p[j] == 0) { g[i * p[j]] = g[i] * 1ll * f[j] % mod; break; } 			g[i * p[j]] = g[i] * 1ll * g[p[j]] % mod; 		} 	} 	for (int i = 2; i <= maxn; i++) g[i] = (g[i - 1] + g[i]) % mod; }  inline int abss(int x) { 	while (x < 0) x += mod; 	return x; }  signed main() { 	t = read(), k = read(); 	work(); 	while (t--) { 		n = read(), m = read(); 		int maxn = min(n, m), ans = 0; 		for (int l = 1, r; l <= maxn; l = r + 1) { 			r = min(n / (n / l), m / (m / l)); 			(ans += abss(g[r] - g[l - 1]) * 1ll * (n / l) % mod * (m / l) % mod) %= mod; 		} 		ans = (ans % mod + mod) % mod; 		cout << ans << 'n'; 	} 	return 0; }