Wipe Your Whiteboards

#include<bits/stdc++.h>
using namespace std;

int T;
long long r, s, q;
long long x, y;

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

// find x, y st. ax + by = gcd(a, b)
long long ext_euclid(long long a, long long b, long long *x, long long *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }

    long long x1, y1;
    long long g = ext_euclid(b,  a % b, &x1, &y1);

    *x = y1; 
    *y = x1 - (a / b) * y1;
    return g;
}

long long f(long long x, long long y) {
    if (x < 0) 
        return x/y;
    return (x + y - 1) / y;
}

int main() {
    cin >> T;
    while (T--) {
        cin >> r >> s >> q;
        long long g = ext_euclid(r, -s, &x, &y);
        x *= q/g;
        y *= -q/g;
        long long u = max(f(1-x, -s/g), f(1-y, r/g));
        cout << x + u*(-s/g) << " " << y + u*(r/g) << endl;
    }
    
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED