CF-992B Nastya Studies Informatics 题解

题目大意

给你一个区间$[l,r]$，求其中有多少点对$(a,b)$，满足$gcd(a,b)=x,lcm(a,b)=y$。

解题思路

说实话，刚开始看到这个题目的时候，觉得这个题目应该不难。

wa了几发之后，人都傻了。

不过还是给我磨过去了，没有看题解。

说实话，我一直都有这种写不出看题解的习惯。

真的不好，但是还是有点难改。。

最近真的注意力不集中。。烦死了

写题也写不出来。

究极自闭。

首先，我们可以根据$a\times b=x\times y$这个性质，可以枚举a来确定b，这时只需要判断是否满足条件即可。

但是这个枚举，我之前就是从l枚举到r，当b<a的时候推出，超时了。。

后来想到，a可以是x的倍数，然后就按照倍数枚举，就过了。

完整代码

#include <iostream>
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {
	return !b ? a : gcd(b, a % b);
}

int main() {
	ll l, r, x, y;
	cin >> l >> r >> x >> y;
	ll mul = x * y, cnt = 0;
	ll a = x, b;
	for (int i = 1; a <= r; i++) {
		a = x * i;
		b = mul / a;
		if (b < a)	break;
		if (a >= l && a <= r && b >= l && b <= r && b * a == mul && gcd(b, a) == x) {
			if (a == b)	cnt++;
			else cnt += 2;
		}
	}
	cout << cnt << endl;
}