Cod sursa(job #257714)

Utilizator bodyionitaIonita Bogdan Constantin bodyionita Data 13 februarie 2009 20:59:35
Problema Algoritmul lui Euclid extins Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 2.41 kb
    program eucl;  
    var f,g:text;  
   t,i,a,b,a1,a2,b1,b2,u,v,x,y,c,r,x0,y0:longint;  
   begin  
     assign(f,'euclid3.in');  
     assign(g,'euclid3.out');  
     rewrite(g);  
     reset(f);  
    readln(f,t);  
     for i:=1 to t do  
      begin  
        readln(f,a,b,c);  
        if (a=0)and(b=0) then writeln(g,0,' ',0)  
        else if (a=0)and(b<>0) then if c mod b=0 then writeln(g,0,' ',c div b)  
                                                 else writeln(g,0,' ',0)  
                               else if (a<>0)and(b=0) then  
                                       if c mod a=0 then writeln(g,c div a,' ',0)  
                                                    else writeln(g,0,' ',0)  
                                                      else begin  
        a1:=abs(a);  
        b1:=abs(b);  
        r:=a1 mod b1;  
        while r<>0 do  
          begin  
           a1:=b1;  
           b1:=r;  
            r:=a1 mod b1  
          end;  
        if abs(c) mod b1<>0 then writeln(g,0,' ',0)  
                       else begin  
                                a2:=abs(a) div b1;  
                               if c>0 then c:=c div b1  
                                      else c:=-(abs(c) div b1);  
                                b2:=abs(b) div b1;  
                                r:=a2 mod b2;  
                                x0:=0;y0:=1;  
                                x:=1;y:=-(a2 div b2);  
                                while r<>0 do  
                                  begin  
                                    a2:=b2;  
                                    b2:=r;  
                                    r:=a2 mod b2;  
                                   u:=x;v:=y;  
                                    x:=x0-(a2 div b2)*x;  
                                    y:=y0-(a2 div b2)*y;  
                                    x0:=u;y0:=v  
                                 end;  
                                   if (a>0)and(b>0) then        writeln(g,x0*c,' ',y0*c);  
                                   if (a>0)and(b<0) then writeln(g,x0*c,' ',-y0*c);  
                                   if (a<0)and(b>0) then writeln(g,-x0*c,' ',y0*c);  
                                   if (a<0) and(b<0) then writeln(g,-x0*c,' ',-y0*c);  
                             end  
                            end;  
      end;  
   close(f);  
   close(g);  
   end.