题意

Hanks博士是BT（Bio-Tech，生物技术）领域的知名专家，他的儿子名叫Hankson。

现在，刚刚放学回家的Hankson正在思考一个有趣的问题。

今天在课堂上，老师讲解了如何求两个正整数c1c1和c2c2的最大公约数和最小公倍数。

现在Hankson认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：

已知正整数a0,a1,b0,b1a0,a1,b0,b1，设某未知正整数x满足：

1、 x和a0a0的最大公约数是a1a1；
2、 x和b0b0的最小公倍数是b1b1。

Hankson的“逆问题”就是求出满足条件的正整数x。

但稍加思索之后，他发现这样的x并不唯一，甚至可能不存在。

因此他转而开始考虑如何求解满足条件的x的个数。

请你帮助他编程求解这个问题。

输入格式

输入第一行为一个正整数n，表示有n组输入数据。

接下来的n行每行一组输入数据，为四个正整数a0，a1，b0，b1a0，a1，b0，b1，每两个整数之间用一个空格隔开。

输入数据保证a0a0能被a1a1整除，b1b1能被b0b0整除。

输出格式

输出共n行。

每组输入数据的输出结果占一行，为一个整数。

对于每组数据：若不存在这样的x，请输出0；

若存在这样的x，请输出满足条件的x的个数；

数据范围

1≤n≤2000
1≤a0,a1,b0,b1≤2∗$10^9$

输入样例：

2
41 1 96 288
95 1 37 1776

输出样例：

6
2

分析

可以根据b1中的质因子$p_i$在a0,a1,b0中的的数量得到x的种类。

设ca0,ca1,cb0,cb1分别为a0,a1,b0,b1包含$p_i$的数量

当(ca0>ca1&&cb0<cb1&&ca1==cb1)  (ca0>ca1&&cb0==cb1&&ca1<=cb1)  (ca0==ca1&&cb0<cb1&&ca1<=cb1) 时，
x中含有p[i]的数量只有一种取法
当(ca0==ca1&&cb0==cb1&&ca1<=cb1)时
x中含有p[i]的数量有cb1-ca1+1种取法
其他情况下不满足问题条件
将这些取法累乘就是x的取法

可以预处理得到20亿以内的所有素数以方便获取b1的质因子，但是实际上可以只获取sqrt(20亿)以内的所有素数，因为如果使用质因数分解最后剩余的数不是1，则这个数就是超过sqrt($2*10^9$)的素数。

代码

#include <iostream>
#include <vector>
using namespace std;

const int N=45000;
int a0,a1,b0,b1,cx,ca0,ca1,cb0,cb1,n,ans;
vector<int> v,p;
int get_num(int big,int sm){
    int res=0;
    while(big%sm==0) res+=1,big/=sm;
    return res;
}

//初始化1-sqrt(20亿)的质数数组
void init(){
    ios::sync_with_stdio(false);
    p.push_back(2); bool flag;
    for(int i=3;i<N;i++){
        flag=0;
        for(int j=0;j<p.size();j++){
            if(i%p[j]==0) {
                flag=1;break;
            }
        }
        if(!flag) p.push_back(i);
    }
}

//获取b1的质因子集合，因为p中只有1-sqrt(20亿)的质数，可能还会有一个质数不在p中
void get_psv(){
    int a=b1;
    for(int i=0;i<p.size();i++){
        if(a%p[i]==0) v.push_back(p[i]);
        while(a%p[i]==0){
            a/=p[i];
        }
    }
    if(a!=1) v.push_back(a);    
}

int main(){
    init(); 
    cin>>n; 
    while(n--){
        ans=1;
        vector<int>().swap(v);
        cin>>a0>>a1>>b0>>b1;
        get_psv();

//        cout<<"vector: "; for(int i=0;i<v.size();i++) cout<<v[i]<<' '; cout<<endl;

        int temp;
        for(int i=0;i<v.size();i++){
            ca0=get_num(a0,v[i]);
            ca1=get_num(a1,v[i]);
            cb0=get_num(b0,v[i]);
            cb1=get_num(b1,v[i]);
//            cout<<ca0<<" "<<ca1<<" "<<cb0<<" "<<cb1<<" temp is "<<endl;
            if(ca0==ca1&&cb0==cb1&&ca1<=cb1) temp=cb1-ca1+1;
            else if(ca0>ca1&&cb0<cb1&&ca1==cb1) temp=1;
            else if(ca0>ca1&&cb0==cb1&&ca1<=cb1) temp=1;
            else if(ca0==ca1&&cb0<cb1&&ca1<=cb1) temp=1;
            else {ans=0;break;}
            // cout<<temp<<endl;
            ans*=temp;
        }
        cout<<ans<<endl;
    }
    return 0;
}