백준 3955번 : 캔디 분배 (c++)

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

3955번: 캔디 분배

문제

창영이는 선영이가 사탕을 공평하게 나누어주지 않으면 친구들을 때릴정도로 사탕을 좋아한다.

따라서, 선영이는 다음 파티에 사용할 사탕을 구매하기 전에 고민을 하기 시작했다.

만약 파티에 K명이 참가한다면, 공정하게 나누어주려면 K×X개를 사야 한다. (X는 자연수) 

선영이는 항상 적어도 한 아이는 사탕을 잃어버린다는 사실을 알고 있다. 그래서 캔디를 하나 더 구매해 총 (K×X+1)개를 구매하려고 한다.

사탕은 봉지 단위로 판매한다. 한 봉지에는 사탕이 총 C개 들어있다. 문제의 조건을 만족하면서 구매할 수 있는 사탕 봉지의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (0 < t < 100) 각 테스트 케이스는 한 줄로 이루어져 있고, K와 C가 공백으로 구분되어져서 주어진다. (1 ≤ K, C ≤ 109) 선영이는 부자가 아니기 때문에 109개를 넘는 사탕 봉지를 구매하지 못한다.

출력

각 테스트 케이스에 대해서 문제의 조건을 만족시키면서 구매할 수 있는 사탕 봉지가 없다면, "IMPOSSIBLE"을 출력한다. 이 경우가 아닌 경우에는 선영이가 구매해야 하는 사탕 봉지의 수를 출력한다. 만약, 가능한 봉지의 수가 여러개라면 아무거나 출력한다.

예제 입력 1 
5
10 5
10 7
1337 23
123454321 42
999999937 142857133
예제 출력 1 
IMPOSSIBLE
3
872
14696943
166666655

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

struct ExtendedGcdResult {
	ll s;
	ll t;
	ll r;

	void print() {
		cout << s << " " << t << " " << r << "\n";
	}
};

int T;
ll A, B;

ExtendedGcdResult eGcd(ll a, ll b) {
	ll s0 = 1, t0 = 0, r0 = a;
	ll s1 = 0, t1 = 1, r1 = b;

	ll temp;
	while (r1 != 0) {
		ll q = r0 / r1;
		temp = r0 - r1 * q;
		r0 = r1, r1 = temp;

		temp = s0 - s1 * q;
		s0 = s1, s1 = temp;

		temp = t0 - t1 * q;
		t0 = t1, t1 = temp;
	}
	ExtendedGcdResult res = { s0,t0,r0 };
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	freopen("input.txt", "r", stdin);
	cin >> T;
	// X: 인당 나눠줄 사탕의 수
	// Y: 사탕 봉지의 수
	// -Ax+By=1;


	for (int i = 0; i < T; i++)
	{
		cin >> A >> B;

		ExtendedGcdResult result = eGcd(-A, B);
		//D = gcd(A,B);
		//Ax+By=C일때 C%D==0이어야 해를 가질 수 있다. : 배주의 항등식
		if (abs(result.r) != 1) {
			cout << "IMPOSSIBLE" << "\n";
		}
		else {
			// x0 = s*C/D;  D가 확장 유클리드에서 나온 마지막 r
			// y0 = t*C.D;
			ll x = result.s * 1 / result.r;
			ll y = result.t * 1 / result.r;

			//x= x0+B/D *K;
			//y= y0-A/D *K;
			while (y <= 0 || x <= 0) {
				x += B;
				y -= -A;
				if (y > 1e9) {
					break;
				}
			}
			if (y > 1e9) {
				cout << "IMPOSSIBLE" << "\n";
			}
			else {
				cout << y << "\n";
			}
		}
	}
	return 0;
}