Mai intai trebuie sa te autentifici.
Cod sursa(job #2724884)
Utilizator | Data | 18 martie 2021 00:37:42 | |
---|---|---|---|
Problema | Algoritmul lui Euclid extins | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.61 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
int a,b,c,s1,s2,t1,t2;
int exgcd(int a, int b){
int c, q, x;
while(b){
c = a % b;
q = a / b;
x = s1 - q*s2;
s1 = s2;
s2 = x;
x = t1 - q*t2;
t1=t2;
t2=x;
a = b;
b = c;
}
return a;
}
int main() {
int nr;
fin>>nr;
for (int i = 0; i<nr; i++){
fin >> a>> b >> c;
s1 = 1;
s2 = 0;
t1 = 0;
t2 = 1;
int x = exgcd(a, b);
if(c%x){
fout << "0 0\n";
} else {
int n = c/x;
fout << s1*n << " "<< t1*n<<'\n';
}
}
return 0;
}