Cod sursa(job #2633880)

Utilizator irimia_alexIrimia Alex irimia_alex Data 9 iulie 2020 00:39:06
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <iostream>

using namespace std;

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

void euclid_extins(int a, int b, int c) {
    int v1[2] = { 1,0 }, v2[2] = { 0,1 }, v[2];
    while (b != 0) {
        int q, r;
        q = a / b;
        r = a % b;
        v[0] = v1[0], v[1] = v1[1];
        v1[0] = v2[0], v1[1] = v2[1];
        v2[0] = v[0] - q * v2[0], v2[1] = v[1] - q * v2[1];
        a = b;
        b = r;
    } if (c % a != 0) { fout << "0 0\n";return; }
    int alfa = v1[0] * c / a;
    int beta = v1[1] * c / a;
    fout << alfa << ' ' << beta << '\n';
}

int main()
{
    int T;
    fin >> T;
    while (T--) {
        int a, b, c;
        fin >> a >> b >> c;
        euclid_extins(a, b, c);
    }

    return 0;
}