题目

link

题解

看到这个东西，想到分解质因数

$\text{输入值} \leq 2\times10^9$，所以根号下＜50000,50000内的指数不是很多，可以考虑枚举每一个质数，根据唯一分解定理来做

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 50000;
int prime[N + 2];
int vis[N + 2];
int cnt = 0;
long long a0, a1, b0, b1;
int main()
{
//	vis[2] = 1;
	for(int i = 2;i <= N;i++)
	{
		if(vis[i]) continue;
		prime[++cnt] = i;
		for(int j = i;j <= N;j += i)
		{
			vis[j] = 1;
		}
	}
	int n;
	scanf("%d", &n);
	while(n --)
	{
		scanf("%lld%lld%lld%lld", &a0, &a1, &b0, &b1);
		long long ans = 1;
		bool ok = 1;
		for(int i = 1;i <= cnt;i++)
		{
			long long d = 0, g = 0, c = 0, f = 0;
			while(a0 % prime[i] == 0)
			{
				a0 /= prime[i];
				c++;
			}
			while(a1 % prime[i] == 0)
			{
				a1 /= prime[i];
				f++;
			}
			while(b0 % prime[i] == 0)
			{
				b0 /= prime[i];
				d++;
			}
			while(b1 % prime[i] == 0)
			{
				b1 /= prime[i];
				g++;
			}
			if(d == g && c == f)
			{
				ans *= (g - f + 1);
			}
			else if(d > g || c < f || ((d != g) && (c != f) && (g != f)))
			{
				ok = 0;
				break;
			}
//			cout << prime[i] << " " << d << " " << g << " " << c << " " << f << endl;
		}
		vector<int> qwq;
		if(a0 != 1) qwq.push_back(a0);
		if(a1 != 1) qwq.push_back(a1);
		if(b0 != 1) qwq.push_back(b0);
		if(b1 != 1) qwq.push_back(b1);
		sort(qwq.begin(), qwq.end());
		for(int i = 0;i < qwq.size();i++)
		{
//			cout << i << endl;
			long long d = 0, g = 0, c = 0, f = 0;
			while(a0 % qwq[i] == 0)
			{
				a0 /= qwq[i];
				c++;
			}
			while(a1 % qwq[i] == 0)
			{
				a1 /= qwq[i];
				f++;
			}
			while(b0 % qwq[i] == 0)
			{
				b0 /= qwq[i];
				d++;
			}
			while(b1 % qwq[i] == 0)
			{
				b1 /= qwq[i];
				g++;
			}
			if(d == g && c == f)
			{
				ans *= (g - f + 1);
			}
			else if(d > g || c < f || ((d != g) && (c != f) && (g != f)))
			{
				ok = 0;
				break;
			}
		}

		if(!ok) cout << 0 << endl;
		else cout << ans << endl;
	}

	return 0;
}