这道题感觉很难想……毕竟数论题好像想到的话基本就没什么事了。
我们要求的数是x，显然可以先设x = p*a1,b1 = t*x,那么b1 = p * t * a1.设s = t * p。
之后我们通过最大公约数和最小公倍数的性质可以先得到，gcd（a0/a1,p） = 1,因为如果二者还有大于1的公约数的话，那么应该存在一个比a1还大的gcd，不成立。同理，我们也可以得到gcd(b1/b0,t) = 1,如果还有大于1的公约数，那么应该存在一个比b1还小的lcm。
这个时候我们已经有暴力的方法了，就是通过枚举s的每一个因子，带入上面两个式子判断是否互质，之后就能计算出合法的x。不过这样的话，会超时，我们考虑进一步优化。
重新观察上面两个式子，因为gcd(b1/b0,s/p) = 1,令m=b1/b0,所以s/p，m必然不存在相同的质因子，我们可以先把s和m相同的质因子筛掉得到新的数l，之后就可以保证s/p必然是l的一个因子。
设a0/a1 = n,那么gcd（n，p） = 1，s/p是l的因子，那么必然p可以表示成r*s/l，那么gcd（r，n） = 1.所以我们只需要把l和n相同的质因子全部筛掉，那么剩下的一个数q的所有因子必然都是合法的了，直接枚举进行计算即可。
注意要特判掉一些不合法情况，分别是n，m，s不为整数和gcd（s/l，n） ！= 1.因为如果出现这种情况的话，（p，n）必然不为1.
看一下代码。
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<cstring> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') #define pr pair<int,int> #define mp make_pair #define fi first #define sc second using namespace std; typedef long long ll; const int M = 20005; const int N = 10000005; const int mod = 13; ll read() { ll ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >='0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } int T,a0,a1,b0,b1,n,m,s; int gcd(int a,int b) { return b ? gcd(b,a%b) : a; } int work(int a,int b) { int k = sqrt(b); rep(i,2,k) { if(!(b % i)) while(!(a % i)) a /= i; while(!(b % i)) b /= i; } if(b != 1) while(!(a % b)) a /= b; return a; } int main() { T = read(); while(T--) { a0 = read(),a1 = read(),b0 = read(),b1 = read(); if(a0 % a1 | b1 % b0 | b1 % a1) { printf("0 "); continue; } m = a0 / a1,n = b1 / b0,s = b1 / a1; int l = work(s,n); if(gcd(max(s/l,m),min(s/l,m)) != 1) { printf("0 "); continue; } int g = work(l,m),cnt = 0,k = sqrt(g); rep(i,1,k) if(!(g % i)) cnt += (i == g / i) ? 1 : 2; printf("%d ",cnt); } return 0; }