Cod sursa(job #3297429)

Utilizator Arhiva_EducationalaArhiva Educationala Arhiva_Educationala Data 22 mai 2025 16:49:24
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>

using namespace std;

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

void euclid( long long a, long long b, long long& x, long long& y, long long& d ) {
    if ( b == 0 ) {
        x = 1;
        y = 0;
        d = a;
    } else {
        euclid( b, a % b, x, y, d );
        long long x2 = y;
        long long y2 = x - (long long)(a / b) * y;

        x = x2;
        y = y2;
    }
}
void solve() {
    long long a, b, c, x, y, d;
    fin >> a >> b >> c;
    euclid( a, b, x, y, d );

    if ( c % d != 0 ) {
        fout << "0 0\n";
    } else {
        fout << x * c / d << ' ' << y * c / d << '\n';
    }
}

int main() {
    int t;
    fin >> t;
    while ( t-- ) solve();
    return 0;
}