Pagini recente » Cod sursa (job #2452796) | Cod sursa (job #3155652) | Cod sursa (job #76838) | Monitorul de evaluare | Cod sursa (job #1781599)
//http://www.infoarena.ro/algoritmul-lui-euclid#comentarii
//http://www.infoarena.ro/problema/euclid3
#include <fstream>
#include <tuple>
#define ull long long int
using namespace std;
ifstream in("euclid3.in");
ofstream out("euclid3.out");
void euclidExtins(ull a, ull b , ull *d, ull *x, ull *y)//a,b numerele noastre , d va fi gcd(a,b)
{
if(b == 0)//daca b= 0 atunc gcd(a,b) = a = *d deci putem lua x = 1 si y = 0 atunci a*1 + b*0 = a
{
*x = 1;
*y = 0;
*d = a;
}
else
{
ull x0,y0;//calculam in x0 si y0(x si y) pentru b si a%b
euclidExtins(b, a%b, d, &x0, &y0);
// b * x0 + a%b * y0 = d si d = a * x + b * y deci
//daca scriem a % b = a - b * c unde c = a/b
//avem b * (x0 - c * y0 - y) = a * (x - y0) si putem lua
//x0 - c * y0 - y = 0 deci y = x0 -c * y0(prin prelucrari)
//si x -y0 = 0 deci x = y0
*x = y0;
*y = x0 - (a/b) * y0;
}
}
tuple<int,int,int> extendedEuclid(int a, int b)//versiunea 2
{
if (b == 0)
return std::make_tuple(a,1,0);
tuple<int,int,int> dxyp = extendedEuclid(b,a%b);
int xp = get<1>(dxyp);
int yp = get<2>(dxyp);
int dp = get<0>(dxyp);
return std::make_tuple(dp,yp,xp- (a/b)*yp);
}
int main()
{
ull x,y,a,b,c,d,t,i;
in >> t;
for( i = 0 ; i < t ; i++)
{
in >> a >> b >> c;
//euclidExtins(a, b, &d, &x, &y);
tuple<int,int,int> dxy = extendedEuclid(a,b);
d = get<0>(dxy);
x = get<1>(dxy);
y = get<2>(dxy);
if (c % d == 0 )//daca d divide pe c inseamna ca si x*c si y*c se divid prin d
out << ( x * c/d) << " " << (y * c/d) << '\n';
else
out << "0 0\n";//altfel nu avem solutie
}
return 0;
}