Pagini recente » Cod sursa (job #1171486) | Cod sursa (job #2459535) | Cod sursa (job #604741) | Cod sursa (job #1144163) | Cod sursa (job #2812958)
#include <bits/stdc++.h>
#define LL long long
using namespace std;
ifstream fin ("euclid3.in");
ofstream fout ("euclid3.out");
LL teste, a, b, cmmdc, target;
LL solX, solY, k;
LL x[70], y[70], s[70];
void euclidExtins(LL a, LL b){
///targetul meu:
/// a * x[i] + b * y[i] = s[i];
/// rest = s[i-2] % s[i-1]
/// cat = s[i-2] / s[i-1]
///s[i] = rest
///x[i] = x[i-2] - cat * x[i-1]
///y[i] = y[i-2] - cat * y[i-1]
k = 3;
s[1] = a, s[2] = b;
x[1] = 1, y[1] = 0;
x[2] = 0, y[2] = 1;
LL rest, cat;
while(s[k-2] % s[k-1] != 0){
rest = s[k-2] % s[k-1];
cat = s[k-2] / s[k-1];
s[k] = rest;
x[k] = x[k-2] - cat * x[k-1];
y[k] = y[k-2] - cat * y[k-1];
k++;
}
k--;
cmmdc = s[k];
solX = x[k];
solY = y[k];
}
int main (){
int teste;
fin >> teste;
while(teste--){
fin >> a >> b >> target;
euclidExtins(a, b);
if(target % cmmdc != 0)
fout << "0 0\n";
else
fout << target / cmmdc * solX << " " << target / cmmdc * solY << "\n";
}
return 0;
}