一、莫比乌斯函数：

其中  是  各互不相等的质数。

二、莫比乌斯函数的一些性质

1、若，则  所有因数的莫比乌斯函数和等于1，否则为0。

2、对于任意正整数 

3、莫比乌斯函数是积性函数

若                            

则   

三、莫比乌斯反演公式

1、若函数  和函数  满足

                                                                            

那么有

                                                                         

2、若函数  和函数  满足

                                                                            

那么有

                                                                         

四、例题

hdu 1695

求  

解法1：莫比乌斯反演

1、设函数  为  的数量，即  

2、设函数  为  的数量，即 

3、对于函数  和 ，显然存在 ，因为左边是所有  的数量，右边是所有 

4、对于函数 ，显然 ，要使 ，显然  都要是  的倍数

5、因为，反演得到 

6、因为  ， 即 ， 所以有 

7、令   ，那么 ，所以有   

8、此时暴力求  即可，但遇到某些毒瘤题（bzoj 2301）就过不去，这时就需要分块优化求 

考虑从小到大枚举 K ，然后求出满足  的最大  x 值，即  ，由于我们枚举 K 是从小到大枚举的，所以对于区间 [k,x] 来说，他在公式的后半部分是相等的，所以可以直接求出这个区间的值，然后 k=x+1 ，直接跳到下一个区间，重复上述步骤，直到 k 大于 min(N/d,M/d)

解法2：利用莫比乌斯函数优秀的性质  

/*
a<=i<=b, c<=j<=d, gcd(i,j)==k的对数
*/
#include <bits/stdc++.h>
#define ll long long //T了就换int 试试
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2e5 + 5;//用板子前先改范围

bool check[MAXN];//值为 false 表示素数，值为 true 表示非素数
int phi[MAXN];//欧拉函数表
int prime[MAXN];//连续素数表
int mu[MAXN + 10];//莫比乌斯函数
int tot;//素数的个数（从0开始
ll sub[MAXN];
void jzk()
{
	memset(check, false, sizeof(check));
	phi[1] = 1;
	mu[1] = 1;
	tot = 0;
	for (int i = 2; i < MAXN; i++) 
	{
		if (!check[i]) 
		{
			prime[tot++] = i;
			phi[i] = i - 1;
			mu[i] = -1;
		}
		for (int j = 0; j < tot; j++) 
		{
			if (i * prime[j] >= MAXN)
				break;
			check[i * prime[j]] = true;
			if (i % prime[j] == 0) 
			{
				phi[i * prime[j]] = phi[i] * prime[j];
				mu[i * prime[j]] = 0;
				break;
			}
			else
			{
				phi[i * prime[j]] = phi[i] * (prime[j] - 1);
				mu[i * prime[j]] = -mu[i];
			}
		}
	}
	for (int i = 1; i < MAXN; i++)
		sub[i] = sub[i - 1] + mu[i];
}


ll solve(ll n, ll m)
{
	ll ans = 0, j = 0;
	int minn = min(n, m);
	//分块
	for (int k = 1; k <= minn; k = j + 1)
	{
		j = min(n / (n / k), m / (m / k));
		ans += (sub[j]- sub[k - 1]) * (n / k) * (m / k);
	}
	/*暴力
	for (int k = 1; k <= minn; k++)
		ans += (ll)mu[k] * (n / k) * (m / k);
	*/
	return ans;
}

int main()
{
    jzk();
    int T, cas = 1;
    sc("%d", &T);
    while (T--)
    {
        ll n, m, d;
        sc("%*d%lld%*d%lld%lld", &n, &m, &d);
        if (n > m) swap(n, m);
        if (!d)
        {
            pr("Case %d: %lld\n", cas++, 0);
            continue;
        }
        n /= d; m /= d;
        ll ans = solve(n, m) - solve(n, n) / 2;
        pr("Case %d: %lld\n", cas++, ans);
    }
}

五、参考博客链接

  https://blog.csdn.net/fo0old/article/details/82020110

https://blog.csdn.net/jk_chen_acmer/article/details/82708274

莫比乌斯反演公式证明：https://blog.csdn.net/litble/article/details/72804050

分块优化证明：https://blog.csdn.net/outer_form/article/details/50590197

贼详细的各种反演和解释：https://www.luogu.org/blog/An-Amazing-Blog/mu-bi-wu-si-fan-yan-ji-ge-ji-miao-di-dong-xi