Cod sursa(job #1089526)

Utilizator kiralalaChitoraga Dumitru kiralala Data 21 ianuarie 2014 19:05:40
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>

using namespace std;

FILE* f=freopen("euclid3.in","r",stdin);
FILE* o=freopen("euclid3.out","w",stdout);

long long a,b,c,n;

void Euclid(long long a, long long b, long long *cmmdc, long long &x1, long long &y1)
{
    if(b==0)
    {
        *cmmdc=a;
        x1=1;
        y1=0;
    }
    else
    {
        long long x0,y0;
        Euclid(b,a%b,cmmdc,x0,y0);
        x1=y0;
        y1=x0-(a/b)*y0;
    }
}

void ComputeAnswer(long long &x, long long &y)
{
    long long x1,y1;
    long long cmmdc;
    Euclid(a,b,&cmmdc,x1,y1);
    if(c%cmmdc!=0) x=y=0;
    else
    {
        x=x1*c/cmmdc;
        y=y1*c/cmmdc;
    }
}

long long main()
{
    long long x,y;
    scanf("%lld",&n);

    for(long long i=0;i<n;++i)
    {
        scanf("%lld%lld%lld",&a,&b,&c);

        ComputeAnswer(x,y);

        printf("%lld %lld\n",x,y);
    }

    return 0;
}