一种很好理解的题解

因为我们的$lcm(b0,x)=b1$
所以$x$一定是$b1$的因数
因此我们只要用一个循环遍历$x$就可以过了
时间复杂度$O(t\sqrt{b1})$
极限复杂度为$2000*\sqrt{2000000000}\approx89442719$可过
代码

#include<iostream>
#include<algorithm>
using namespace std;
long long t,a0,a1,b0,b1,ans;
long long lcm(long long a,long long b){
    return a/__gcd(a,b)*b;
}
long long gcd(long long a,long long b){
    return __gcd(a,b);
}
//注:__gcd是由头文件algorithm提供的函数,用于计算两数最大公因数
//根据最大公因数与最小公倍数之积等于两数之积,就能通过gcd算出lcm
int main(){
    cin>>t;
    while (t--){
        cin>>a0>>a1>>b0>>b1;
        ans=0;
        for (int x=1;x*x<=b1;x++){
            if (b1%x==0){//不能整除就不满足假设
                if (gcd(x,a0)==a1&&lcm(x,b0)==b1){//x本身
                    ans++;
                }
                if (b1/x!=x&&gcd(b1/x,a0)==a1&&lcm(b1/x,b0)==b1){//b1对于x的另一个因数,注意b1/x不能等于x,不加会在第一个点WA
                    ans++;
                }
            }
        }
        cout<<ans<<endl;
    }
	return 0;
}

制作不易,求点赞