Pagini recente » Monitorul de evaluare | Rating FII-Pintilie Andrei (Pintilie_Andrei) | Cod sursa (job #2492270) | Profil popoiu.george | Cod sursa (job #2800835)
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;
using ll = long long;
using cd = complex<double>;
constexpr ll mod = 1e9 + 7, maxn = 3e5 + 10;
pair<ll, ll> euclid_extins(ll x, ll y);
int main() {
ifstream f("euclid3.in");
ofstream g("euclid3.out");
int t;
f >> t;
while (t--) {
ll x, y, z, a, b;
f >> x >> y >> z;
tie(a, b) = euclid_extins(x, y);
ll G = a * x + b * y;
if (z % G)
g << 0 << ' ' << 0 << '\n';
else
g << (a * (z / G)) << ' ' << (b * (z / G)) << '\n';
}
return 0;
}
pair<ll, ll> euclid_extins(ll x, ll y) {
ll g = 1;
while (x % 2 == 0 && y % 2 == 0) x /= 2, y /= 2, g *= 2;
ll u = x, v = y, a = 1, b = 0, c = 0, d = 1;
do {
for (int i = 0; i < 2; ++i) {
while (u % 2 == 0) {
u /= 2;
if (a % 2 == 0 && b % 2 == 0)
a /= 2, b /= 2;
else
a = (a + y) / 2, b = (b - x) / 2;
}
swap(a, c);
swap(b, d);
swap(u, v);
}
if (u >= v)
u -= v, a -= c, b -= d;
else
v -= u, c -= a, d -= b;
} while (u != 0);
return make_pair(c, d);
}