Cod sursa(job #2534842)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 30 ianuarie 2020 23:24:05
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>

#define llg     long long

std::ifstream input ("euclid3.in");
std::ofstream output("euclid3.out");

int euclid(int a, int b, int &x, int &y) {
    if (b == 0) {
        y = 0;
        x = 1;
        return a;
    }   int ans = euclid(b, a%b, x, y);
    int v = y;
    y = x - (a/b)*y;
    x = v;
    return ans;
}

void solve(int a, int b, int c) {
    int aux1, aux2;
    int gcd = euclid(a, b, aux1, aux2);

    if (c%gcd) {
        output << 0 << ' ' << 0 << '\n';
        return;
    }

    c /= gcd, a /= gcd, b /= gcd;
    euclid(a, b, aux1, aux2);
    output << aux1*c << ' ' << aux2*c << '\n';
}

int main()
{
    int T;  input >> T;
    while (T--) {
        int a, b, c;
        input >> a >> b >> c;
        solve(a, b, c);
    }

    return 0;
}