#include [HTML_REMOVED]

using namespace std;
int gcd(int a,int b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
int main()
{
int n;
cin>>n;
while(n–)
{
//推公式来稍微降低一点复杂度
//gcd(a,b)=c<–>gcd(a/c,b/c)=1
int a0,a1,b0,b1;
cin>>a0>>a1>>b0>>b1;
int ans=0;
for(int i=1;i<=b1/i;i)
{
if(b1%i==0) //必要条件
{
if(gcd(i/a1,a0/a1)==1&&
(i%(b1/b0)==0)&&
(gcd(b1/b0,b1/i)==1)&&
i%a1==0)
ans;

    if(gcd(b1/(a1*i),a0/a1)==1&&
    ((b1/i)%(b1/b0)==0)&&
     (gcd(b1/b0,i)==1)&&
          (b1/i)%a1==0&&
               i!=b1/i)
     ans++;

}
}
    if(ans==0)
    cout<<'0'<<endl;
    else
    cout<<ans<<endl;

}
return 0;
}

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla