Cod sursa(job #2924637)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 6 octombrie 2022 21:20:35
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.58 kb
#include <bits/stdc++.h>

using namespace std;

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

int gcd(int A,int B,int &X,int &Y)
{
    if(B==0)
    {
        X=1;
        Y=0;
        return A;
    }
    int X0,Y0,D;
    D=gcd(B,A%B,X0,Y0);
    X=Y0;
    Y=X0-(A/B)*Y0;
    return D;
}

int main()
{
    int n;
    in>>n;
    for(int i=0;i<n;i++)
    {
        int A,B,C;
        in>>A>>B>>C;
        int X,Y;
        int D=gcd(A,B,X,Y);
        if(C%D)
        {
            out<<"0 0\n";
        }
        else
        {
            out<<X*(C/D)<<' '<<Y*(C/D)<<'\n';
        }
    }
}