Cod sursa(job #1262991)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 13 noiembrie 2014 20:00:14
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <cstdio>
using namespace std;

ofstream g("euclid3.out");
long a,b,c,r,cat,n,aux,i,j,x,y,ok,xa,ya;

long modul(long k)
{
    if (k<0)
        return -k;
    return k;
}
long cmmdc(long a,long b)
{
    long r=1;
    while (r!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main()
{
    freopen("euclid3.in","r",stdin);
    scanf("%ld",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%ld%ld%ld",&a,&b,&c);
        ok=0;
        if (b>a)
        {
            aux=a;
            a=b;
            b=aux;
            ok=1;
        }
        if (b==0)
        {
            if (c%a==0)
                g<<c/a<<' '<<0<<'\n';
            else
                g<<"0 0\n";
        }
        else if (c%cmmdc(modul(a),modul(b))==0)
        {
            xa=1;ya=0;x=0;y=1;

            while (b)
            {
                cat=a/b;
                r=a%b;
                aux=x;
                x=xa-cat*x;
                xa=aux;
                aux=y;
                y=ya-cat*y;
                ya=aux;
                a=b;
                b=r;
            }
            if (ok==1)
            {
                aux=xa;
                xa=ya;
                ya=aux;
            }
            g<<xa*(c/a)<<' ';
            g<<ya*(c/a)<<'\n';
        }
        else
            g<<"0 0\n";
    }
    g.close();
    return 0;
}