目录
莫比乌斯函数
定义
性质
性质1
性质2
线性筛
莫比乌斯反演
形式1
形式2
证明
例题
实战
莫比乌斯函数
定义
莫比乌斯函数的定义可以用一个分段函数简单表示：
对这个定义式做个解释：
当 x = 1 时，函数值为 1；
当 分解质因数后，质因子的最高次数为 1 时，函数值为 其中 为 分解出的质因子的个数；
其余情况函数值取 0。
性质
可以证明，莫比乌斯函数是一种积性函数，因此拥有积性函数的一般性质：
1.若将 x 表示为质因数分解式 ，则有；
2.若 f(x) 为积性函数，且，则 f(x) 为完全积性函数。
除此之外，莫比乌斯函数还有两个非常重要的特殊性质：
性质1
（其中 d|n 表示 d 是 n 的因子；[] 内表达式为真时，值为 1；表达式为假时，值为 0）
浅浅地证明一下：
当 n = 1 时，d 只能取 1，等式左边为，等式右边也为 1，显然成立；
当 n > 1 时，将 n 分解为，结合莫比乌斯函数的定义，可以得出只有当所有质因子次数为 1 的 n 的因子的函数值才不为 0，这样每个因子就可以用来表示，其中 k 是 n 的质因子个数，i 是取 n 中不同质因子的个数，这样有：
再由组合数的性质：奇数项之和等于偶数项之和，且值为。
以 k 为奇数为例，可以将上式进行如下变换，
k 为偶数时同理。
这样当 n > 1 时，性质 1 也成立。
性质2
（其中 是欧拉函数，也是一种积性函数）
证明就先略过，等写了迪利克雷卷积后再补吧（ヽ(゜▽゜））
线性筛
int primes[N], mu[N], cnt;bool st[N];void get_mu(){mu[1] = 1;for(int i = 2; i <= n; i++){if(!st[i]){mu[i] = -1;primes[cnt++] = i;}for(int j = 0; j < cnt && primes[j] * i <= n; j++){st[primes[j] * i] = true;if(i % primes[j] == 0){mu[primes[j] * i] = 0;break;}else mu[primes[j] * i] = mu[primes[j]] * mu[i];}}}
莫比乌斯反演
莫比乌斯反演最早是通过找规律进行猜测的结论，后来经过严格证明得到了现在非常重要的数学定理。
在算法竞赛中，莫比乌斯反演有两种非常常用的形式，设 f(x)，g(x) 是定义在正整数集上的两个函数：
形式1
若函数 f(x)，g(x) 满足
，
则有
。
形式2
若函数 f(x)，g(x) 满足
，
则有
。
证明
这里仅对形式 1进行证明，形式 2 的证明类似。
考虑对进行变换：
由于，有：
由于内层枚举的是，与 无关，因此可以将放入内层，得：
再交换一下求和次序：
此时内层枚举 ，与无关，将提出来，得：
根据莫比乌斯函数性质 1，，那么整个大求和只有时有非零值，因此上式最终只有一项。
即得证。
例题
题目大意：给定 n 和 m，求 且 的(x, y)有多少对。
解题思路：对于这种与 gcd 相关的题，可以不需要使用莫比乌斯反演的标准形式（毕竟推起来令人头大）。
将题目所求用数学式子表示出来为
利用莫比乌斯函数性质 1，可以转换成
再将求和次序进行交换，
由于 d 是 gcd(i, j) 的因子，d 一定也是 i 和 j 的因子，每个 d 的倍数的个数在 [1, n] 和 [1, m] 分别为和，因此后两个求和就可以转换成，此时 d 就可以转换成从 1 枚举到，最终计算式为。
实战
题目链接：YY的GCD - 洛谷
题目大意：给定 n 和 m，求 且 为质数的(x, y)有多少对。
解题思路：还是抽象成一个式子：。
根据约数个数的性质，化为，
利用莫比乌斯函数性质 1，化为，
再像例题一样进行转换，得。
到这计算式已经可以解决问题了，但是照这样枚举会超时，只能再想办法进行优化这个式子了。
令，则。式子变为，
再改变一下求和次序，得。
对于这个式子，我们可以令，则就可以直接用代替了。
这样前面部分可以用整除分块进行计算，复杂度为 ，后面部分预处理筛出莫比乌斯函数后，枚举质数 p，每个质数 p 的倍数 T 都可以预处理出来，即每次加上 ，再用个前缀和预处理一下就可以 计算了。
AC代码：
#include <bits/stdc++.h>#define lowbit(x) (x & -x)#define mid (l + r >> 1)using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<int, int> PII;typedef pair<ll, ll> PLL;const int INF = 0x3f3f3f3f;const ll LLF = 0x3f3f3f3f3f3f3f3f;const int mod = 1000000007;const int N = 10000005;ll primes[N], mu[N], sum[N];bool st[N];int cnt;void get_mu(){ // 线性筛莫比乌斯函数mu[1] = 1;for(int i = 2; i <= N; i++){if(!st[i]){mu[i] = -1;primes[cnt++] = i;}for(int j = 0; j < cnt && primes[j] * i <= N; j++){st[primes[j] * i] = true;if(i % primes[j] == 0){mu[primes[j] * i] = 0;break;}else mu[primes[j] * i] = -mu[i];}}}void init(){ // 预处理前缀和for(int i = 0; i < cnt; i++){for(int j = 1; primes[i] * j <= N; j++){sum[j * primes[i]] += mu[j];}}for(int i = 1; i <= N; i++){sum[i] += sum[i - 1];}}int main(){//freopen("input.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);get_mu();init();int t;cin >> t;while(t--){int n, m;cin >> n >> m;if(n > m) swap(n, m); // 让 n <= m, 方便计算ll ans = 0;for(int l = 1, r; l <= n; l = r + 1){ // 整除分块r = min(n / (n / l), m / (m / l));ans += (sum[r] - sum[l - 1]) * (n / l) * (m / l);}cout << ans << endl;}return 0;}
