Cod sursa(job #2848095)

Utilizator AdrianCrainicuAdrian Crainicu AdrianCrainicu Data 12 februarie 2022 09:51:07
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <string>


using namespace std;

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

void e(int a, int b, int& d, int& x, int& y) {
    if (b == 0) {
        d = a, x = 1, y = 0;
    }
    else {
        int x0, y0;
        e(b, a % b, d, x0, y0);
        x = y0;
        y = x0 - (a / b) * y0;
    }
}

int main() {
    int n;
    fin >> n;

    int op[100][3];
    for (int i = 0; i < n; i++) {
        fin >> op[i][0] >> op[i][1] >> op[i][2];
    }

    for (int i = 0; i < n; i++) {
        int a, b, c;
        a = op[i][0];
        b = op[i][1];
        c = op[i][2];

        int d=0, x=0, y=0;

        e(a, b, d, x, y);

        //cout << "xyd: " << x << " " << y << " " << d << endl;

        int xFin = x * (c / d),
            yFin = y * (c / d);

        if (c % d != 0) fout << 0 << " " << 0 << endl;
        else fout << xFin << " " << yFin << endl;

        //cout << a * xFin + b * yFin;

        //cout << x << " " << y << endl;

    }
}