Cod sursa(job #1979136)

Utilizator PescaruVictorPescaru Victor PescaruVictor Data 9 mai 2017 19:17:46
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <map>
using namespace std;

ifstream fin ("euclid3.in");
ofstream fout ("euclid3.out");

pair<long long int, long long int> euclid (long long int a, long long int b, long long int c);

long long int a, b, c;

int main()
{
    int nrt;
    pair <long long int, long long int> rez;
    fin>>nrt;
    for(int i=1; i<=nrt; ++i)
    {
        fin>>a>>b>>c;
        rez=euclid(a, b, c);
        fout<<rez.first<<' '<<rez.second<<'\n';
    }
    return 0;
}


pair<long long int, long long int> euclid (long long int a, long long int b, long long int c)
{
    long long int d=a, i=b, r;
    pair <long long int, long long int> x, y, aux;
    x.first=1;
    x.second=0;
    y.first=0;
    y.second=1;
    if(i)
    {
        r=1;
    }
    else r=0;
    while(r)
    {
        aux.first=x.first-(d/i)*y.first;
        aux.second=x.second-(d/i)*y.second;
        x=y;
        y=aux;

        r=d%i;
        d=i;
        i=r;

    }
    if(c%d!=0)
    {
        x.first=0;
        x.second=0;
    }
    else
    {
        x.first=x.first*(c/d);
        x.second=x.second*(c/d);
    }
    return x;

}