[C++] 백준 21568번

#include <iostream>
#include <stack>

using namespace std;

int gcd(int a, int b);
void EEuclidean(int x, int y);
stack<pair<int, int>> S; // 몫, 나머지

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int a, b, c, x, y, k;
	cin >> a >> b >> c;

	if (c % gcd(a, b))
	{
		cout << -1;
		return 0;
	}
	else
		EEuclidean(1, 0);

	x = S.top().first;
	y = S.top().second;
	k = c / gcd(a, b);

	cout << x * k << ' ' << y * k << '\n';


	return 0;
}

int gcd(int a, int b)
{
	if (b == 0)
		return a;
	else
	{
		S.push(make_pair(a / b, a % b));
		return gcd(b, a % b);
	}
}


void EEuclidean(int x, int y)
{
	if (S.empty())
	{
		S.push(make_pair(x, y));
		return;
	}
		
	int q = S.top().first;
	int new_x = y;
	int new_y = x - (y * q);
	S.pop();

	EEuclidean(new_x, new_y);
}