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 的个数。请你帮助他编程求解这个问题。
输入输出格式输入格式：
第一行为一个正整数 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
输出样例#1：
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。
NOIP 2009 提高组 第二题
Solution：
首先，我们知道这两个等式：gcd(a0,x)=a1,lcm[b0,x]=b1
于是，我们可以设：x=a1∗p,b1=x∗t
于是有：a1∗p∗t=b1
所以我们令：b1/a1=s
则：p∗t=s
即：t=s/p
又由最大公约数与最小公倍数的定义与性质可得：
gcd(a0/a1,p)=1,gcd(b1/b0,t)=1
所以我们令：a0/a1=m,b1/b0=n
则有：(p,m)=1,(s/p,n)=1
这就是第一个结论，我们称其为结论一。事实上，我们其实已经可以由结论一整理出可以AC的方法，即用sqrt(s)的复杂度枚举s的因数，然后将每个因数放到结论一中，看看是否成立，再统计所有符合结论一的因数的个数，然后输出即可。这种算法的复杂度是：O(sqrt(s)*log(s)*n)。这样其实也能卡过数据，但是还是没有达到理论上的通过。所以我们还要继续优化。
我们考虑(s/p,n)=1。如果s/p与n有相同质因数，则意思那个无法使(s/p,n)=1成立。于是，我们可以将s与n所有相同的质因数从s中去掉，得到剩余的数l（这一点还是很需要技巧的，在程序中会有解析）。于是，s/p就必须是l的约数。
我们继续考虑(p,m)=1。因为s/p是l的约数，那么p就一定可以表示为这样的形式：
p=(s/l)∗r
即：p一定是s/l的倍数（因为s/p是l的约数）。而r也必须是l的约数。于是就又有：
r∣l,(r,m)=1
这就是第二个结论，我们称其为结论二。而解决结论二的方法便很明显了。我们可以用与解决结论一相似的方法，将l与m所有相同的质因数从l中去掉，得到剩余的数q。那么这样，所有符合条件的r都是q的因数了。然后，我们可以用sqrt(q)的复杂度枚举q的所有因数，输出q的因数个数就行了。这样，复杂度便降到了：O((sqrt(s)+log(s))*n)，从理论来说也不会超时了。
还有一点需要注意，那就是特判没有符合要求的x的情况。这种情况出现只有四种可能：
1、s不为整数2、m不为整数3、n不为整数4、(s/l,m)≠1，即因为p是s/l的倍数，所以无论r取何值，都会有(p,m)≠1加上这四个特判，这道题便做完了。
总结一下，这道题，代码虽不长，但是思路需要很精细，也难想到，是一道不错的题。
（无优化，枚举d1的因子做为x，并判断互质，戳）代码：
1 // luogu-judger-enable-o2 2 #include 3 #define il inline 4 #define ll long long 5 #define debug printf("%d %s\n",__LINE__,__FUNCTION__) 6 using na����,ǰ��mespace std; 7 ll n,a0,a1,b0,b1,ans; 8 il ll gi() 9 {10 ll a=0;char x=getchar();bool f=0;11 while((x<'0'||x>'9')&&x!='-')x=getchar();12 if(x=='-')x=getchar(),f=1;13 while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();14 return f?-a:a;15 }16 il ll gcd(int a,int b){return !b?a:gcd(b,a%b);}17 int main()18 {19 n=gi();20 while(n--){21 a0=gi(),a1=gi(),b0=gi(),b1=gi();22 if(a0%a1|b1%b0|b1%a1){printf("0\n");}23 else if(a0==a1&&a1==b1&&b0==b1)printf("1\n");24 else {25 ans=0;26 int m=sqrt(b1);27 for(int i=1;i*i<=b1;i++)28 if(b1%i==0){29 if(i%a1==0&&gcd(i/a1,a0/a1)==1&&gcd(b1/b0,b1/i)==1)ans++;30 int j=b1/i;31 if(i==j)continue;32 if(j%a1==0&&gcd(j/a1,a0/a1)==1&&gcd(b1/b0,b1/j)==1)ans++; 33 }34 printf("%lld\n",ans);35 }36 }37 return 0;38 }
（优化）代码：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include<string> 7 using namespace std; 8 int ssqrt; 9 int cf(int a,int b)//去掉a中与b共有的质因数。思想：将b质因数分解，同时将a中与b共有的质因数去掉。10 {11 ssqrt=sqrt(b);12 for(int i=2;i<=ssqrt;i++)//sqrt(b)复杂度质因数分解b13 {14 if(b%i==0)while(a%i==0)a/=i;//去掉a中与b共有的质因数，将a分解15 while(b%i==0)b/=i;//将b质因数分解16 }17 if(b!=1)while(a%b==0)a/=b;//注意：此时b可能还不是1，因为b可能有比sqrt(b)更大的质因数，但至多只有一个，且它的次幂至多是1。所以如果b不是1，那就只能是一个质数。于是此时继续分解a。18 return a;//返回剩下的a19 }20 int gcd(int a,int b){return b==0?a:gcd(b,a%b);}//辗转相除求最大公约数21 int main()22 {23 int a0,a1,b0,b1;24 int gs;25 int m,n,s,l,q;26 scanf("%d",&gs);27 int cnt;28 while(gs--)29 {30 scanf("%d%d%d%d",&a0,&a1,&b0,&b1);31 if(a0%a1|b1%b0|b1%a1){printf("0\n");continue;}//如果m、n、s中有小数，则直接输出0。这里的代码用到了一些位运算32 m=a0/a1,n=b1/b0,s=b1/a1;l=cf(s,n);//求出m、n、s，然后求出l33 if(gcd(max(s/l,m),min(s/l,m))!=1){printf("0\n");continue;}//如果不互质，则直接输出034 q=cf(l,m);cnt=0,ssqrt=sqrt(q);//求出q，开始枚举q的因数，求出q的因数个数35 for(int i=1;i<=ssqrt;i++)if(q%i==0)cnt+=i==q/i?1:2;//这里注意，如果i==q/i，则只加1，否则加236 printf("%d\n",cnt);//输出37 }38 return 0;39 }