自动搬运

查看原文

来自洛谷，原作者为

	Loyal_Soldier 一只小菜蛙 | 一只爱玩PVZ杂交版的蛙 | 天生我菜必有用，千金散尽还复来 | 这个人很菜，请忽略他的红名 | 小号@kaikai_qwq

搬运于2025-08-24 23:09:29，当前版本为作者最后更新于2025-08-19 14:41:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

设 $\text{calc}(a, b)$ 表示满足 $x\le y, 1\le x\le a, 1\le y\le b, y - x = \gcd(x, y)$ 限制的正整数数对的数量，根据容斥原理可得最终答案为 $\text{calc}(b, d) - \text{calc}(a - 1, d) - \text{calc}(b, c - 1) + \text{calc}(a - 1, c - 1)$。

我们发现，满足限制的数对 $(x, y)$ 都满足 $x = p\times \gcd(x, y), y = q\times \gcd(x, y)$，并且 $q - p = 1$。因此，对于所有形如 $(p\times \gcd(x, y), (p + 1)\times \gcd(x, y))$ 的数对都满足条件。

那么，只需要枚举 $\gcd(x, y)$ 就行了，设当前枚举的 $\gcd(x, y)$ 为 $g$，则答案增加 $\min(\lfloor \frac{a}{g}\rfloor, \lfloor \frac{b}{g}\rfloor - 1)$。但是直接枚举会超时，需要整除分块优化。

代码

#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
int a, b, c, d; 
int calc(int x, int y)
{
	int ans = 0;
	for(int l = 1, r;l <= min(x, y);l = r + 1)
	{
		r = min(x / (x / l), y / (y / l));
		ans += (r - l + 1) * min(x / l, y / l - 1);
	}//整除分块
	return ans;
}
signed main()
{
	cin >> a >> b >> c >> d;
	cout << calc(b, d) - calc(a - 1, d) - calc(b, c - 1) + calc(a - 1, c - 1);//容斥
	return 0;
}