2．Hankson的趣味题(son.pas/c/cpp)【问题描述】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：根据最大公约数的定义，X必定为最大公约数的倍数，那么我们可以去枚举a1的倍数，然后去验证最大公约数和最小公倍数是否符合条件。
期待分数：50。
程序1：vara0,a1,b0,b1,i,j,n,k,x,tot:longint;function gcd(a,b:longint):longint;beginif b=0 then exit(a) else exit(gcd(b,a mod b));end;beginreadln(n);for k:=1 to n dobegintot:=0;readln(a0,a1,b0,b1);for i:=1 to (b1 div a1) dobeginx:=i*a1;if b1 mod x=0 thenif gcd(a0,x)=a1 thenif (b0*x) div (gcd(b0,x))=b1 then begin inc(tot); end;end;writeln(tot);end;end.思路2：根据最小公倍数和最大公约数分解质因数指数的特殊关系进行优化。
比如两个数，分解质因数可以得到以下的式子A=p1^a1+p2^a2+p3^a3……B=p1^b1+p2^b2+p3^a3……例如6和21就可以分解成6=2^1+3^1+5^0+7^0……21=2^0+3^1+5^0+7^1……则最大公约数=2^(min(a1,b1))+3^(min(a2,b2))+5^(min(a3,b3))+7^(min(a4,b4))…最小公倍数=2^(max(a1,b1))+3^(max(a2,b2))+5^(max(a3,b3))+7^(max(a4,b4))…那么我们可以先将b1分解质因数，在根据最大公约数和最小公倍数在指数上的关系，进行搜索。
期待分数：100程序2：varp,x,c:array[0..1000] of longint;a0,a1,b0,b1,i,j,k,m,tot,t,n:longint;function gcd(a,b:longint):longint;beginif b=0 then exit(a) else exit(gcd(b,a mod b));end;procedure dfs(i,sum:longint);varmax,j:longint;beginif i>m thenbegininc(tot);p[tot]:=sum;exit;end;max:=sum;dfs(i+1,max);for j:=1 to c[i] dobeginmax:=max*x[i];dfs(i+1,max);end;end;procedure work(b:longint); var i,p:longint;begini:=2;p:=b;while i<=sqrt(p) dobeginif p mod i=0 thenbegininc(m);x[m]:=i;c[m]:=0;repeatinc(c[m]);p:=p div i;until p mod i<>0;end;inc(i);end;if p<>1 thenbegininc(m);x[m]:=p;c[m]:=1;end;dfs(1,1);end;readln(n);for i:=1 to n dobeginreadln(a0,a1,b0,b1);fillchar(p,sizeof(p),0);fillchar(x,sizeof(x),0);fillchar(c,sizeof(c),0);m:=0;tot:=0;t:=0;work(b1);for j:=1 to tot doif (gcd(p[j],a0)=a1) and ((p[j] div gcd(p[j],b0) * b0)=b1) then inc(t);writeln(t);end;end.思路三：和思路二有异曲同工之妙。
我们可以先预处理trunc(sqrt(2000000000))以内的质数，然后每读入一组数据，初始答案ans=1,然后我们循环质数，看a0、a1、b0、b1里面有多少个该质数因子，并且将这四个数分别消去所有该质数因子。
我们设求出来的该因子个数分别是t1、t2、t3、t4。
如果数据合法，那么t1>=t2,t3<=t4。
根据最大公约数和最小公倍数的定义，我们要求的数所拥有的该质因子个数s必须要同时满足以下限制条件：若t1>t2,则s=t2若t1=t2，则s>=t2若t3<t4,则s=t4若t3=t4，则s<=t4这样，我们或者求出了s的范围，要么证明了不存在合法数字。
如果s存在合法取值，我们就将ans乘上s的合法取值个数，否则直接输出0。
注意：如果循环结束后，a0>1或b1>1，那么此时a0或b1一定是超过我们枚举的数字范围的质数。
这时我们特殊判断一下就行了。
我们的时间复杂度是循环质数复杂度+分解因数复杂度。
分解因数最坏是该数为2的若干次方，所以复杂度的上限是log(2000000000)，很小。
最慢的点在0.3秒以内出解。
程序3program son;var i,j,k,l,m,n,p,q,l2,r2,r,s,t,a0,a1,b0,b1,ans:longint;prime:array[0..60000] of longint;need:array[0..60000] of longint;pd:boolean;function pri(x:longint):boolean;var g:longint;for g:=2 to trunc(sqrt(x)) doif x mod g=0 then exit(false);exit(true);end;beginp:=1;prime[1]:=2;for i:=3 to 50000 do if pri(i) then begininc(p);prime[p]:=i;end;read(n);for t:=1 to n dobeginread(a0,a1,b0,b1);ans:=1;fillchar(need,sizeof(need),255);q:=p;pd:=true;for i:=1 to p dobeginl:=0;r:=0;l2:=0;r2:=0;while a0 mod prime[i]=0 dobegininc(l);a0:=a0 div prime[i];end;while a1 mod prime[i]=0 dobegininc(r);a1:=a1 div prime[i];end;while b0 mod prime[i]=0 dobegininc(l2);b0:=b0 div prime[i];end;while b1 mod prime[i]=0 dobegininc(r2);b1:=b1 div prime[i];end;if l>r then need[i]:=r;if l2<r2 thenbeginif (need[i]>-1)and(need[i]<>r2) then beginpd:=false;break;end;need[i]:=r2;end;if need[i]=-1 thenif r2<r thenbeginpd:=false;break;end else ans:=ans*(r2-r+1);end;if i=p thenif a0>1 thenbegininc(i);prime[i]:=a0;l:=0;r:=0;l2:=0;r2:=0;while a0 mod prime[i]=0 dobegininc(l);a0:=a0 div prime[i];end;while a1 mod prime[i]=0 dobegininc(r);a1:=a1 div prime[i];end;while b0 mod prime[i]=0 dobegininc(l2);b0:=b0 div prime[i];end;while b1 mod prime[i]=0 dobegininc(r2);b1:=b1 div prime[i];end;if l>r then need[i]:=r;if l2<r2 thenbeginif (need[i]>-1)and(need[i]<>r2) thenbeginpd:=false;end;need[i]:=r2;end;if need[i]=-1 thenif r2<r thenbeginpd:=false;end else ans:=ans*(r2-r+1);dec(i);end;if i=p thenif b1>1 thenbegininc(i);prime[i]:=b1;l:=0;r:=0;l2:=0;r2:=0;while a0 mod prime[i]=0 dobegininc(l);a0:=a0 div prime[i];end;while a1 mod prime[i]=0 dobegininc(r);a1:=a1 div prime[i];end;while b0 mod prime[i]=0 dobegininc(l2);b0:=b0 div prime[i];end;while b1 mod prime[i]=0 dobegininc(r2);b1:=b1 div prime[i];end;if l>r then need[i]:=r;if l2<r2 thenbeginif (need[i]>-1)and(need[i]<>r2) thenbeginpd:=false;end;need[i]:=r2;end;if need[i]=-1 thenif r2<r thenbeginpd:=false;end else ans:=ans*(r2-r+1);dec(i);end;if not pd then writeln(0) else writeln(ans);end;end.。
