Cod sursa(job #2455406)

Utilizator chivoiugabrielChivoiu Gabriel chivoiugabriel Data 11 septembrie 2019 18:22:28
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>

using namespace std;

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

void cmmmdcit(int a,int b,int &d,int &x,int &y)
{
    int r,r0,r1,x0,x1,y0,y1,q;
    r0=a,r1=b,x0=1,y0=0,x1=0,y1=1;
    while(r1!=0)
    {
        q=r0/r1;
        r=r0-r1*q;
        r0=r1;
        r1=r;
        x=x0-x1*q;
        x0=x1;
        x1=x;
        y=y0-y1*q;
        y0=y1;
        y1=y;
    }
    d=r0;
    x=x0;
    y=y0;
}

int main()
{
    int a,b,c,t,x,y,d;
    fin>>t;
    for(int i=0;i<t;i++)
    {
        fin>>a>>b>>c;
        cmmmdcit(a,b,d,x,y);
        if(c%d!=0)
            fout<<"0 0"<<'\n';
        else
        {
            x=x*(c/d);
            y=y*(c/d);
            fout<<x<<" "<<y<<'\n';
        }
    }
    fin.close();
    fout.close();
    return 0;
}