思路
由 “x 和 a0 的最大公约数是 a1;x 和 b0 的最小公倍数是 b1。”
知,x是b1的约数
所以先求出所有b1的约数,再枚举所有约数x,判断x是否满足gcd(x,a0)==a1 且 x和b0的最小公倍数是否是b1即可
如何求x和b0的最小公倍数?
x*b0/gcd(x,b0)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
int n;
int a0,a1,b0,b1;
int gcd(int a,int b){
return b ? gcd(b,a%b) : a;
}
int main(){
int T;
cin >> T;
while(T--){
scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
vector<int> c;
for(int i=1;i<=b1/i;i++){
if(b1%i==0){
c.push_back(i);
if(i!=b1/i) c.push_back(b1/i);
}
}
int res=0;
for(auto x : c){
if(gcd(x,a0)==a1 && (LL)x*b0/gcd(x,b0)==b1 ) res++;
}
cout << res << endl;
}
return 0;
}