Pagini recente » Cod sursa (job #90810) | Cod sursa (job #2283699) | Cod sursa (job #1969186) | Cod sursa (job #278400) | Cod sursa (job #665408)
Cod sursa(job #665408)
#include <iostream>
#include <fstream>
#include <cassert>
#include <algorithm>
struct pair {
long x, y;
pair(long _x, long _y) : x(_x), y(_y) {}
};
void print(pair p)
{
std::cout << "(" << p.x << ", " << p.y << ")" << std::endl;
}
void printGcd(pair p, long a, long b)
{
std::cout << "GCD is " << a * p.x + b * p.y << std::endl;
}
pair euclid(long a, long b)
{
long init_a = a, init_b = b;
assert(a >= b);
pair prev(1, 0);
pair curr(0, 1);
// print(prev);
// print(curr);
while(b != 0)
{
print(curr);
long q = a / b;
long r = a % b;
pair old = curr;
curr.x = prev.x - q * curr.x;
curr.y = prev.y - q * curr.y;
prev = old;
a = b;
b = r;
}
// printGcd(prev, init_a, init_b);
return prev;
}
int main(int argc, char ** argv)
{
std::ifstream fin("euclid3.in");
std::ofstream fout("euclid3.out");
if(!fin || !fout)
return -1;
unsigned int n;
fin >> n;
for(unsigned int i = 0; i < n; i++)
{
long a, b, c;
fin >> a >> b >> c;
if(a < b) std::swap(a, b);
pair sol = euclid(a, b);
if(a < b) std::swap(sol.x, sol.y);
long gcd = a * sol.x + b * sol.y;
if(c % gcd != 0)
{
fout << "0 0" << std::endl;
}
else
fout << sol.x * (c / gcd) << " " << sol.y * (c / gcd) << std::endl;
}
return 0;
}