Cod sursa(job #942283)

Utilizator smaraldaSmaranda Dinu smaralda Data 21 aprilie 2013 19:11:19
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include<stdio.h>
const long long INF=2000000000;
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;
    long long solx,soly;
    scanf("%d",&tc);
    while(tc)
        {
            scanf("%d%d%d",&a,&b,&c);
            euclid(x0,y0,gcd);
            if(c%gcd)
                printf("0 0\n");
            else
                {
                    for(k=1;;k++)
                        {
                            solx=((long long)x0+(k*b)/gcd)*(c/gcd);
                            soly=((long long)y0-(k*a)/gcd)*(c/gcd);
                            if(solx>=-INF && soly<=INF && solx<=INF && soly>=-INF)
                                break;
                        }
                    printf("%I64d %I64d\n",solx,soly);
                }
            tc--;
        }
    return 0;
}