Cod sursa(job #324785)

Utilizator IoannaPandele Ioana Ioanna Data 17 iunie 2009 13:42:29
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 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 long k;
int s=0;
printf("%ld %ld\n",x0*(c/gcd),y0*(c/gcd));
}

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;
}