Cod sursa(job #715442)

Utilizator algotrollNume Fals algotroll Data 17 martie 2012 11:36:01
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<cstdio>

void double_assign(int *plv1,int *plv2,   int rv1,int rv2)
{
    *plv1 = rv1;
    *plv2 = rv2;
}

int main()
{
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
    int nN;
    scanf("%d", &nN);
    for (int i=1; i<=nN; i++)
    {
        int a,b,c;
        scanf("%d %d %d", &a, &b, &c);
        int prevx=1,prevy=0 ,x=0,y=1;
        while (b!=0)
        {
            int cat = a/b;
            double_assign(&x,&prevx,   prevx-x*cat,x);
            double_assign(&y,&prevy,   prevy-y*cat,y);
            double_assign(&a,&b,   b,a%b);
        }//a*prevx+b*prevy == gcd (now a==gcd)
        if (c%a==0)
            printf("%d %d\n", prevx * c/a, prevy * c/a);
        else
            printf("0 0\n");
    }
    return 0;
}