program hankson;

var

n,i,m,k,ans,a0,a1,b0,b1:longint;

function gys(a,b:longint):longint;

var ch:longint;

begin

if a<b then begin

ch:=a;

a:=b;

b:=ch;

end;

if b=0 then exit(a);

gys:=gys(b,a mod b);

end;

function gbs(a,b:longint):longint;

var x:longint;

begin

x:=gys(a,b);

gbs:=a*(b div x);

end;

begin

readln(m);

for i:=1 to m do begin

ans:=0;

readln(a0,a1,b0,b1);

if(gys(a1,b1)=1)and(a1<>1)then begin

writeln(0);

continue;

end;

k:=b1 div b0;

n:=k;

while((gys(n,a0)<>a1)or(gbs(n,b0)<>b1))and(n<=b1)do

n:=n+k;

k:=n;

while n<=b1 do begin

if(gys(n,a0)=a1)and(gbs(n,b0)=b1)then inc(ans);

n:=n+k;

end;

writeln(ans);

end;

readln;

end.

有神马地方可以优化的吗？？？

我随便写的有90分。。

思路不是这样的，先把他们分解成质因子再做。。

已经AC了，谢了

回复 地毯ptwuyuhuai 的帖子

我是质因数分解做的，为什么最后一个点会超时啊？