ac1029.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1029;
var
  d,ans:array[0..99]of cardinal;
  n,i,a,b,depth,t:cardinal;
  succeed:boolean;
function min(a,b:cardinal):cardinal;
  begin
    if a<b then min:=a else min:=b;
  end;
function max(a,b:cardinal):cardinal;
  begin
    if a>b then max:=a else max:=b;
  end;
function gcd(a,b:cardinal):cardinal;
  var
    t:cardinal;
  begin
    if a<b then begin t:=a;a:=b;b:=t;end;
    repeat
      t:=a mod b;a:=b;b:=t;
    until t=0;
    gcd:=a;
  end;
procedure subtract(x:cardinal);
  var
    t:cardinal;
  begin
    t:=gcd(b,x);
    a:=x div t*a-b div t;b:=b div t*x;
    if a=0 then exit;
    t:=gcd(a,b);
    a:=a div t;b:=b div t;
  end;
procedure search(l:byte);
  var
    i,ta,tb:cardinal;
  begin
    if l=depth then begin
      if (a>1) or (b<=d[l-1]) or (b>=ans[l]) then exit;
      ans:=d;ans[l]:=b;
      succeed:=true;
    end
    else
      for i:=max(d[l-1]+1,trunc(b/a)+1) to min(trunc((depth-l+1)/(a/b)+1e-6),ans[depth]-1) do begin
        d[l]:=i;ta:=a;tb:=b;
        subtract(i);
        search(l+1);
        a:=ta;b:=tb;
      end;
  end;
begin
  d[0]:=1;
  read(n);
  for i:=1 to n do begin
    fillchar(ans,sizeof(ans),255);
    read(a,b);t:=gcd(a,b);a:=a div t;b:=b div t;
    depth:=0;
    succeed:=false;
    repeat
      inc(depth);
      search(1);
    until succeed;
    for a:=1 to depth-1 do
      write(ans[a],' ');
    writeln(ans[depth]);
  end;
end.