Cod sursa(job #2593174)
Utilizator | Data | 3 aprilie 2020 08:30:40 | |
---|---|---|---|
Problema | Algoritmul lui Euclid extins | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.52 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream f("euclid3.in");
ofstream g("euclid3.out");
long long i, n, X1, X2, Y1, Y2, x, y, rest1, rest2, rest, d, val, cat;
int main()
{
f >> n;
for(i = 1; i <= n; ++ i)
{
f >> rest1 >> rest2 >> d;
if(rest1 == 0 || rest2 == 0)
{
if(rest1 == 0)
{
if(d % rest2 == 0)
g << "0 " << d / rest2 << "\n";
else
g << "0 0" << "\n";
}
else
{
if(d % rest1 == 0)
g << d / rest1 << " 0" << "\n";
else
g << "0 0" << "\n";
}
}
else
{
val = __gcd(rest1, rest2);
X1 = 1;
X2 = 0;
Y1 = 0;
Y2 = 1;
if(d % val != 0)
g << "0 0" << "\n";
else
{
while(rest1 % rest2 != 0)
{
cat = rest1 / rest2;
rest = rest1 % rest2;
rest1 = rest2;
rest2 = rest;
x = X1 - cat * X2;
y = Y1 - cat * Y2;
X1 = X2;
X2 = x;
Y1 = Y2;
Y2 = y;
}
g << X2 * (d / val) << " " << Y2 * (d / val) << "\n";
}
}
}
return 0;
}