题目描述

　　Hanks 博士是BT (Bio-Tech，生物技术) 领域的知名专家，他的儿子名叫Hankson。现在，刚刚放学回家的Hankson 正在思考一个有趣的问题。今天在课堂上，老师讲解了如何求两个正整数c1 和c2 的最大公约数和最小公倍数。现在Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数a0,a1,b0,b1，设某未知正整数x 满足：

1、x 和a0 的最大公约数是a1；

2、x 和b0 的最小公倍数是b1。

Hankson 的“逆问题”就是求出满足条件的正整数x。但稍加思索之后，他发现这样的x 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的x 的个数。请你帮助他编程求解这个问题。

输入格式

　　输入文件名为 son.in。第一行为一个正整数n，表示有n 组输入数据。接下来的n 行每行一组输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证a0 能被a1 整除，b1 能被b0 整除。

输出格式

　　输出文件 son.out 共n 行。每组输入数据的输出结果占一行，为一个整数。对于每组数据：若不存在这样的 x，请输出0；若存在这样的 x，请输出满足条件的x 的个数；

样例数据 1

输入

2

41 1 96 288

95 1 37 1776

输出

6

2

「说明」第一组输入数据，x 可以是9、18、36、72、144、288，共有6 个。第二组输入数据，x 可以是48、1776，共有2 个。

备注

「数据范围」

对于 50%的数据，保证有1≤a0，a1，b0，b1≤10000 且n≤100。

对于 100%的数据，保证有1≤a0，a1，b0，b1≤2,000,000,000 且n≤2000。

 

sol：有一种能得90pts的优秀暴力，i 从1~sqrt（n）枚举，判断 i 和 b1/i 是否可行 （非常好打）

/*原式 b0*x/gcd(b0,x) = b1  -->b0*x = gcd(b0,x)*b1  -->b0*x/b1 = gcd(b0,x)  -->gcd(b0,x) = b0*x/b1  -->gcd(b1/x,b1/b0) = 1*/#include 
       
        using namespace std;typedef long long ll;inline ll read(){    ll s=0;    bool f=0;    char ch=' ';    while(!isdigit(ch))    {        f|=(ch=='-'); ch=getchar();    }    while(isdigit(ch))    {        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();    }    return (f)?(-s):(s);}#define R(x) x=read()inline void write(ll x){    if(x<0)    {        putchar('-'); x=-x;    }    if(x<10)    {        putchar(x+'0'); return;    }    write(x/10);    putchar((x%10)+'0');    return;}#define W(x) write(x),putchar(' ')#define Wl(x) write(x),putchar('\n')ll a0,a1,b0,b1;inline ll gcd(ll x,ll y){    return (!y)?(x):(gcd(y,x%y));}inline int Solve(int x){    return ((gcd(a0,x)==a1)&&gcd(b1/x,b1/b0)==1)?1:0;}int main(){    int i,T;    R(T);    while(T--)    {        R(a0); R(a1); R(b0); R(b1);        int ans=0;        for(i=1;i<=sqrt(b1);i++) if(b1%i==0)        {            ans=ans+Solve(i);            if(i*i!=b1) ans+=Solve(b1/i);        }        Wl(ans);    }    return 0;}/*input241 1 96 28895 1 37 1776output62*/
       

 

正解是这样的，暴力枚举b1的质因数：对于一个质因数 k

对于 a0中若有 k^c0，a1中有k^c1：那么因为gcd（a0，x）=a1，所以c0必须不小于c1，否则无解，如果c0=c1，那么x中k的系数可以是任意一个大于等于c0的数，反正gcd后还是k^c0，如果c0>c1，那么x中k的系数必须是c1

对于b0中若有 k^c2，b1中有k^c3：那么因为lcm（b0，x）=b1，所以c2必须不大于c3，否则无解，如果c2=c3，那么x中k的系数可以是任意一个小于等于c3的数，反正lca后还是k^c3，如果c2<c3，那么x中k的系数必须是c3

Ps：想清楚后代码也很简单（关键是要想明白）

/*原式 b0*x/gcd(b0,x) = b1  -->b0*x = gcd(b0,x)*b1  -->b0*x/b1 = gcd(b0,x)  -->gcd(b0,x) = b0*x/b1  -->gcd(b1/x,b1/b0) = 1      gcd(x,a0)==a1    lcm(x,b0)==b1    //b1一定是x的整倍数，而x一定是a1的整倍数*/#include 
       
        using namespace std;typedef int ll;inline ll read(){    ll s=0;    bool f=0;    char ch=' ';    while(!isdigit(ch))    {        f|=(ch=='-'); ch=getchar();    }    while(isdigit(ch))    {        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();    }    return (f)?(-s):(s);}#define R(x) x=read()inline void write(ll x){    if(x<0)    {        putchar('-'); x=-x;    }    if(x<10)    {        putchar(x+'0'); return;    }    write(x/10);    putchar((x%10)+'0');    return;}#define W(x) write(x),putchar(' ')#define Wl(x) write(x),putchar('\n')const int N=50005;int a0,a1,b0,b1,ans;bool Bo[N];int Prim[N];inline void Pre_Prime(){    int i,j;    for(i=2;i<=50000;i++)    {        if(!Bo[i]) Prim[++*Prim]=i;        for(j=1;j<=*Prim&&Prim[j]*i<=50000;j++)        {            Bo[Prim[j]*i]=1;            if(i%Prim[j]==0) break;        }    }    return;}inline void Solve(int x){    int c0=0,c1=0,c2=0,c3=0;    while(a0%x==0){a0/=x; c0++;}    while(a1%x==0){a1/=x; c1++;}    while(b0%x==0){b0/=x; c2++;}    while(b1%x==0){b1/=x; c3++;}    if(c0
        
         c3)    {        ans=0;        return;    }    if(c0==c1&&c2==c3)    {        if(c1<=c3) ans*=c3-c1+1;        else ans=0;    }    else if(c0>c1&&c2
         
          1) Solve(b1);        Wl(ans);    }    return 0;}/*input241 1 96 28895 1 37 1776output62input210 10 10 105 1 2 10output10*/