P1072 [NOIP 2009 提高组] Hankson 的趣味题

题目的意思很简单，找到一个 ，其满足

那我们可以看出，一个必要条件是： 是 的倍数，同时 是 的约数。那我们可以枚举 的所有满足条件的数，时间复杂度 ，极端情况下， 是能去到 。

首先，枚举的范围是可以降到 的，但是其实我们可以进一步的转换思路，与其枚举 ，不如试着枚举 使得 成立，这样的话可以得到

那么，我们从1枚举到 找出它的所有因子，每次使用试除法找到一对因子 与 ,然后判断其与 的乘积是否满足条件即可。 这样，总的枚举复杂度不超过

和 的判定使用辗转相除法即可。

#include<iostream>

int gcd(int a, int b)
{
	return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a, int b)
{
	return a / gcd(a, b) * b;
}

int main()
{
	std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
	int n;
	std::cin >> n;
	while (n--)
	{
		int a_0, a_1, b_0, b_1;
		std::cin >> a_0 >> a_1 >> b_0 >> b_1;
		int ans = 0;
		int m = b_1 / a_1;
		for (int i = 1; i*i <= m; i++)
		{
			if (m % i == 0)
			{
				int x = i * a_1;
				int y = m / i * a_1;
				if (gcd(x, a_0) == a_1 && lcm(x, b_0) == b_1)
				{
					ans++;
				}
				if (x!=y&&gcd(y, a_0) == a_1 && lcm(y, b_0) == b_1)
				{
					ans++;
				}
			}
		}
		std::cout << ans << std::endl;
	}
}