Wipe Your Whiteboards

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
ll ee(ll a,ll b, ll ca, ll cb, ll xa, ll xb, ll&x,ll&y){
	if(cb==0){
		x=xa;
		if(b==0)y=0;
		else y=(ca-a*xa)/b;
		return ca;
	}
	else return ee(a,b,cb,ca%cb,xb,xa-(ca/cb)*xb,x,y);
}

pair<ll,pair<ll,ll>> solve(ll a,ll b,ll c){
	if(c==0)return {1,{0,0}};
	if(a==0&&b==0)return {0,{0,0}};
	ll x,y;
	ll g=ee(a,b,a,b,1,0,x,y);
	if(abs(c)%g>0)return {0,{0,0}};
	return {g,{x*(c/g),y*(c/g)}};
}

int main(){
	int Tn;
	cin>>Tn;
	while(Tn--){
		ll a,b,c;
		cin>>a>>b>>c;
		auto v=solve(a,b,c);
		ll g = abs(v.F);
		b/=g;
		a/=g;
		ll A = v.S.F;
		ll B = v.S.S;
		ll k=-A/b;
		A+=k*b;
		B-=k*a;
		while(A<=0)A-=b,B+=a;
		if(B<=0){
			k=B/a;
			A+=k*b;
			B-=k*a;
		}
		while(B<=0)A-=b,B+=a;
		cout<<A<<' '<<B<<'\n';
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED