Cod sursa(job #324779)

Utilizator IoannaPandele Ioana Ioanna Data 17 iunie 2009 13:10:43
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<stdio.h>
#define max 2000000000
int t;
long a,b,c;

void read()
{
scanf("%ld%ld%ld",&a,&b,&c);
}

void euclid(long &x1,long &x2,long &x3)
{
long y1,y2,y3,q,r1,r2,r3;
x1=y2=1;
x2=y1=0;
x3=a;
y3=b;
while (y3)
      {
       q=x3/y3;
       r1=x1-q*y1;
       r2=x2-q*y2;
       r3=x3-q*y3;
       x1=y1;
       x2=y2;
       x3=y3;
       y1=r1;
       y2=r2;
       y3=r3;
      }
}

void solutie(long x0,long y0,long gcd)
{
long long x,y;
long k;
int s=0;
k=1;
while (!s)
      {
       x=x0+k*b/gcd;
       x=x*c/gcd;
       y=y0-k*a/gcd;
       y=y*c/gcd;
       if (x>max)
          k--;
       else if (y>max)
                k++;
            else {
                  printf("%lld %lld\n",x,y);
                  s=1;
                 }
      }
}

int main()
{
freopen("euclid3.in","r",stdin);
freopen("euclid3.out","w",stdout);
scanf("%d",&t);
int i;
long x1,x2,x3;
for (i=1;i<=t;i++)
    {
     read();
     euclid(x1,x2,x3);
     if (c%x3!=0)
         printf("0 0\n");
     else solutie(x1,x2,x3);
    }
return 0;
}