Cod sursa(job #2258008)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 10 octombrie 2018 18:51:52
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <bits/stdc++.h>

std::ifstream InFile("euclid3.in");
std::ofstream OutFile("euclid3.out");

int Q;

void Euclid(int a, int b, int &X, int &Y, int &GCD) {
    if (b==0) {
        X = 1;
        Y = 0;
        GCD = a;
        return;
    }   Euclid(b, a%b, X, Y, GCD);

    int aux = Y;
    Y = X - (a/b)*Y;
    X = aux;
}

void Citire() {
    InFile >> Q;
}

void Rezolvare() {
    int a, b, c, x, y, gcd;
    while(Q--) {
        InFile >> a >> b >> c;
        Euclid(a, b, x, y, gcd);
        if (c%gcd)
            OutFile << 0 << ' ' << 0 << '\n';
        else
            OutFile << x * (c/gcd) << ' ' << y * (c/gcd) << '\n';
    }
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}