Cod sursa(job #1171792)

Utilizator TataruTataru Mihai Tataru Data 16 aprilie 2014 13:06:27
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#define inFile "euclid3.in"
#define outFile "euclid3.out"

using namespace std;

long long cmmdc(long long a,long long b,long long &x,long long &y)
{
    long long x0,y0,d;
    if(b==0){x=1,y=0;return a;}
	d=cmmdc(b,a%b,x0,y0);
	x=y0;
	y=x0-(a/b)*y0;
	return d;
}

int main()
{
    long long t,a,d,b,c,k,x,y;
    ifstream fin(inFile);
    ofstream fout(outFile);
    fin>>t;
    for(k=1;k<=t;k++)
    {
        fin>>a>>b>>c;
        d=cmmdc(a,b,x,y);
        if(c%d==1){
            fout<<"0 0\n";
            continue;}
        else
        {
            x*=c/d;
            y*=c/d;
            fout<<x<<" "<<y<<"\n";
        }
    }
    fin.close();
    fout.close();
}