Cod sursa(job #1166118)

Utilizator a.raduAndrei Radu a.radu Data 3 aprilie 2014 11:25:56
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <cstdio>

using namespace std;
long x,c[10000],t,y,a,b,i,cc,cm,xx,yy,u,jx,jk;
int euc(long a, long b)
    {
    if (b>0) { jx++; c[jx]=a/b; }
    if (a*b>0)
        return euc(b,a%b);
            else
            return a+b;
    }
int main()
{
freopen("euclid3.in","r",stdin);
freopen("euclid3.out","w",stdout);
scanf("%ld",&t);
for (u=1; u<=t; u++)
    {
    scanf("%ld%ld%ld",&a,&b,&cc); jx=0; jk=0;
    if (a<b)
        {
        x=a; a=b; b=x;
        jk=1;
        }
    cm=euc(a,b);
    x=0; y=0;
    if (cc%cm==0)
    {
    x=1; y=0;
    for (i=jx; i; i--)
        {
        xx=y;
        yy=x-c[i]*y;
        x=xx; y=yy;
        }
    x*=cc/cm; y*=cc/cm;
    if (jk==1)
        {jk=x; x=y; y=jk;}
    }
    printf("%ld %ld\n",x,y);
    }
return 0;
}