算法提高课

达达正在破解一段密码，他需要回答很多类似的问题：

对于给定的整数 a,ba,b 和 dd，有多少正整数对 x,yx,y，满足 x≤a，y≤bx≤a，y≤b，并且 gcd(x,y)=dgcd(x,y)=d。

作为达达的同学，达达希望得到你的帮助。

输入格式

第一行包含一个正整数 nn，表示一共有 nn 组询问。

接下来 nn 行，每行表示一个询问，每行三个正整数，分别为 a,b,da,b,d。

输出格式

对于每组询问，输出一个正整数，表示满足条件的整数对数。

数据范围

1≤n≤500001≤n≤50000,
1≤d≤a,b≤500001≤d≤a,b≤50000

输入样例：

2
4 5 2
6 4 3

输出样例：

3
2

提示:gcd(x,y)gcd(x,y) 返回 x，yx，y 的最大公约数。

核心思路：首先我们需要知道莫比乌斯函数的相关定义：

我们对于原式子化简可得：x'<=\(\frac{a}{d}\),y‘<=\(\frac{b}{d}\),gcd(x',y')=1;所以整个问题转换为了求x'和y'互质的对数，在一定的范围内。这里可以用到容斥原理了，也就是合法的对数=总对数-不合法的对数。

总对数很好求：我们令a'=\(\frac{a}{d}\),b'=\(\frac{b}{d}\),所以总对数就是a'b';

那不合法的对数我们怎么转换为呢，我们就分情况：找出一个公共的质因子，找出两个公共的质因子......

使用数学符号就可以表示为：\(\frac{a'}{2}*\frac{b'}{2}\),\(\frac{a'}{6}\frac{b'}{6}\)......。然后我们需要注意下，我们使用容斥原理是需要找集合，所以我们可以吧把只有一个质因子的定义为\(S_1\),有两个定义为\(S_2\),以此类推。

所以我们使用容斥原理的总表示就是：

其实我们会发现这个是正好符合我们莫比乌斯函数的定义的。因为我们规定只要有一个质因子就是-1(次数不可以大于1）,两个就是1，以此类推。就是\((-1)^k\).
接下来就是数论分块的思想了。不记得一定要去看博客,顺便看下莫比乌斯反演的博客，加深印象.
因为我们的\(\frac{a'}{i}\)和\(\frac{b'}{i}\)在一定的区间内这个函数值是不会变的，所以我们需要求一下前缀和u(x)函数的。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 6e5 + 10;
int primes[N], st[N];
int mobius[N],sum[N];
int cnt;
void Init()
{
    mobius[1]=1;
	for (int i = 2;i < N;i++)
	{
		if (!st[i])
		{
			primes[cnt++] = i;
			mobius[i] = -1;
		}
		for (int j = 0;primes[j] * i < N;j++)
		{
			int t = primes[j] * i;
			st[t] = 1;
			if (i % primes[j] == 0)//说明至少含有两个primes[j]
			{
				mobius[t] = 0;
				break;
			}
			mobius[t] = -mobius[i];
		}
	}
	for (int i = 1;i < N;i++)
		sum[i] = sum[i - 1] + mobius[i];
}
int main()
{
	Init();
	int T;
	cin >> T;
	while (T--)
	{
		LL res = 0;
		int a, b, d;
		cin >> a >> b >> d;
		a /= d;
		b /= d;
		int n = min(a, b);//这个和我们的定义有关可以看下那个推导的公式
		for (int l = 1, r;l <= n;l = r + 1)
		{
			r = min(n, min(a / (a / l), b / (b / l)));//这里有人差不多，反正可以理解为取交集
			res += (sum[r] - sum[l - 1]) * (LL)(a / l) * (b / l);
		}
		cout << res << endl;
	}
}