Cod sursa(job #942271)

Utilizator smaraldaSmaranda Dinu smaralda Data 21 aprilie 2013 18:59:41
Problema Algoritmul lui Euclid extins Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<stdio.h>
int a,b,c,a1,b2,b3,b1,a2,a3,c1,c2,c3;
void euclid (int &x0, int &y0, int &gcd)
{
    int r1,r2,r3,q;
    a1=1,a2=0,a3=a;
    b1=0,b2=1,b3=b;
    while(b3)
        {
            q=a3/b3;
            r1=a1-q*b1;
            r2=a2-q*b2;
            r3=a3-q*b3;
            a1=b1;
            a2=b2;
            a3=b3;
            b1=r1;
            b2=r2;
            b3=r3;
        }
    x0=a1; y0=a2; gcd=a3;
}

long long abs (long long x)
{
    if(x<0) return -x;
    return x;
}
int main()
{
    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);
    int tc,x0,k,y0,gcd;
    scanf("%d",&tc);
    while(tc)
        {
            scanf("%d%d%d",&a,&b,&c);
            euclid(x0,y0,gcd);
            if(c%gcd)
                printf("0 0\n");
            else
                printf("%d %d\n",(x0+b/gcd)*(c/gcd),(y0-a/gcd)*(c/gcd));
            tc--;
        }
    return 0;
}