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;
}

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;
        while (x <= 0 || y <= 0) {
            x += -s/g;
            y += r/g;
        }
        while (x > -s/g && y > r/g) {
            x += s/g;
            y -= r/g;
        }
        cout << x << " " << y << endl;
    }
    
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED