Wipe Your Whiteboards

#include <iostream>
#include <utility>
typedef long long ll;

// return gcd(a, b), and c and d for which ac + bd = gcd(a, b)
std::pair<ll, std::pair<long long, long long>> ext_euc(ll a, ll b) {
	if (a < b) {
		auto res = ext_euc(b, a);
		return {res.first,{res.second.second, res.second.first}};
	} else {
		ll k = a / b;
		if (a == k * b) {
			return {b, {0, 1}};
		} else {
			auto sub = ext_euc(b, a - k * b);
			return {sub.first, {sub.second.second, sub.second.first - k * sub.second.second}};
		}
	}
}


int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);

	ll t;
	std::cin >> t;

	for (ll j = 0; j < t; ++j) {
		ll r, s, q;
		std::cin >> r >> s >> q;
		// find a and b such that
		// ar + bs = q
		// and a>=1 and b>=1 and they are minimal
		auto res = ext_euc(r, -s);
		ll gcd = res.first;
		ll a = res.second.first;
		ll b = res.second.second;
		a *= q / gcd;
		b *= q / gcd;
		// ar - bs = q
		ll bg = r / gcd;
		ll ag = -s / gcd;
		//std::cout << a << ' ' << b << ' ' << ag << ' ' << bg << '\n';
		ll k = (ag - a) / ag;
		a += ag * k;
		b -= bg * k;
		k = (a-1) / ag;
		a -= k * ag;
		b += k * bg;
		if (b >= 0) {
			k = 1 + (b / bg);
			a += k * ag;
			b -= k * bg;
		}
		std::cout << a << ' ' << -b << '\n';
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED