Cod sursa(job #2975739)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 7 februarie 2023 12:36:05
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <bits/stdc++.h>

using namespace std;

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

void euclidExtins(int n, int m, int& d, int& x, int& y) {
    if (m == 0) {
        d = n;
        x = 1;
        y = 0;
        return;
    }

    int x0, y0;
    euclidExtins(m, n % m, d, x0, y0);
    x = y0;
    y = x0 - (n / m) * y0;

}

void solve(int a, int b, int c) {
    int d, x, y;
    euclidExtins(a, b, d, x, y);
    if (c % d != 0)
        fout << 0 << ' ' << 0 << '\n';
    else
        fout << x * (c / d) << ' ' << y * (c / d) << '\n';
}

int main() {
    int n;
    fin >> n;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        solve(a, b, c);
    }
    return 0;
}