Nu aveti permisiuni pentru a descarca fisierul grader_test18.in
Cod sursa(job #2841128)
Utilizator | Data | 29 ianuarie 2022 12:26:19 | |
---|---|---|---|
Problema | Algoritmul lui Euclid extins | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.78 kb |
#include <bits/stdc++.h>
using namespace std;
#ifdef INFOARENA
#define cin fin
#define cout fout
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
#endif // INFOARENA
using ll = long long;
ll extgcd(ll a, ll b, ll* x, ll* y) {
if(a == 0) {
*x = 0;
*y = 1;
return b;
}
ll x1, y1;
ll gcd = extgcd(b % a, a, &x1, &y1);
*x = y1 - (b / a) * x1;
*y = x1;
return gcd;
}
int main()
{
int t;
cin >> t;
while(t--) {
ll a, b, c, x, y;
cin >> a >> b >> c;
ll gcd = extgcd(a, b, &x, &y);
if(abs(c) % abs(gcd) == 0) {
int coeff = c / gcd;
cout << coeff * x << " " << coeff * y << "\n";
} else cout << "0 0\n";
}
return 0;
}