题目#
题解#
看到这个东西，想到分解质因数
$\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;
}