Pagini recente » Cod sursa (job #532372) | Cod sursa (job #751921) | Cod sursa (job #32614) | Istoria paginii runda/simulare_oni_9_1/clasament | Cod sursa (job #2916829)
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#define int long long
using namespace std;
ifstream fin ("euclid2.in");
ofstream fout ("euclid2.out");
const int MAX_Q = 105;
int qcnt, startX, startY, target;
int cmmdc, solX, solY;
int cnt, x[100], y[100], s[100];
void euclidExtins(){
/**
My goal:
startX * x[i] + startY * y[i] = s[i]
Initialize:
s[1] = startX
x[1] = 1
y[1] = 0
s[2] = startY
x[2] = 0
y[2] = 1
Recurrence:
s[i] = s[i-2] % s[i-1]
x[i] = x[i-2] - x[i-1] * (s[i-2] / s[i-1])
y[i] = y[i-2] - y[i-1] * (s[i-2] / s[i-1])
**/
if(startX == 0){
cmmdc = startY;
solX = 0;
solY = 1;
return;
}
if(startY == 0){
cmmdc = startX;
solX = 1;
solY = 0;
return;
}
cnt = 3;
s[1] = startX, x[1] = 1, y[1] = 0; /// startX * 1 + startY * 0 = startX
s[2] = startY, x[2] = 0, y[2] = 1; /// startX * 0 + startY * 1 = startY
while(s[cnt-2] % s[cnt-1] != 0){
s[cnt] = s[cnt-2] % s[cnt-1];
x[cnt] = x[cnt-2] - x[cnt-1] * (s[cnt-2] / s[cnt-1]);
y[cnt] = y[cnt-2] - y[cnt-1] * (s[cnt-2] / s[cnt-1]);
cnt++;
}
cnt--;
cmmdc = s[cnt];
solX = x[cnt];
solY = y[cnt];
return;
}
signed main (){
ios_base::sync_with_stdio(false);
fin.tie(nullptr), fout.tie(nullptr);
fin>>qcnt;
while(qcnt--){
fin>>startX>>startY>>target;
euclidExtins();
if(target % cmmdc != 0)
fout<<"0 0\n";
else{
target /= cmmdc;
fout<<target * solX<<" "<<target * solY<<"\n";
}
}
return 0;
}