2020-01-02 11:13 已编辑字节跳动_电商_服务架构

关注

莫比乌斯反演

一、莫比乌斯函数：

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

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

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);
    }
}