취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11635번 문제인 Wipe Your Whiteboards이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/11635 

2 이상인 정수 R, -2 이하인 정수 S, 1 이상인 정수 Q가 주어질 때 AR+BS=Q를 만족하는 1 이상인 정수 A와 B의 쌍을 구하는 문제이다.

S가 음수인 것이 거슬리므로, S 대신 -S를 이용하고 -1 이하인 정수 -B를 구하는 것으로 문제를 바꾸어 풀자.

AR+BS=Q를 만족시키는 정수 A와 B는 extended euclidean algorithm(확장 유클리드 알고리즘)을 이용하여 구할 수 있다. 문제 조건에서 Q는 R과 S의 gcd의 배수라고 주어졌으므로 이를 만족시키는 정수 A와 B의 쌍은 항상 존재한다.

이제 문제조건에 맞는 답을 구하기 위해, 다음과 같은 순서로 수를 변경해주자.

1) A가 0 이하의 정수라면 0 이상으로 바꿔준다.

2) (B를 신경쓰지 않고) A를 minimal한 양수로 바꾼다.

3) -B가 음수가 되면서 A를 최대한 적게 증가시키게 수를 변경한다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <tuple>
using namespace std;
typedef long long ll;

tuple<ll, ll, ll> extgcd(ll a, ll b, ll p, ll q, ll r, ll s) {
	if (b == 0) return make_tuple(a, p, r);
	ll tmp = a / b;
	return extgcd(b, a - tmp * b, q, p - tmp * q, s, r - tmp * s);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) {
		ll R, S, Q; cin >> R >> S >> Q;
		S *= -1;
		ll g, p, r; tie(g, p, r) = extgcd(R, S, 1, 0, 0, 1);
		Q /= g;
		p *= Q, r *= Q;
		
		ll unitp = S / g, unitr = R / g;

		if (p < 0) {
			ll tmp = abs(p) / unitp + 1;
			p += tmp * unitp, r -= tmp * unitr;
		}

		if (1) {
			ll tmp = (p - 1) / unitp;
			p -= tmp * unitp, r += tmp * unitr;
		}

		if (r >= 0) {
			ll tmp = r / unitr + 1;
			p += tmp * unitp, r -= tmp * unitr;
		}

		cout << p << ' ' << -r << '\n';
	}
}