백준 3955 캔디 분배 C++

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

3955번: 캔디 분배

한 봉지에 사탕 C개가 들어 있고, 친구들이 K명 올 때 K * X + 1개의 사탕을 준비하여면 몇 봉지의 사탕을 사야하는 지 문제입니다. 문제를 바꿔 생각하면 K * X + 1 = 1 mod K 이므로 결국 A봉지 준비한다면 C * A = 1 mod K 와 동일합니다. 그러므로 유클리드 알고리즘으로 C^-1 mod K를 구하면 됩니다.

(10^9 개 넘는 봉지 못 산다는 조건 안 보고 풀다가 몇 번 틀렸다....)

 

#include <iostream>

using namespace std;

int t;
long long k, c;
// c^-1 mod k 구하면 됨
// 안되는 경우는 gcd(c,k)!=1 인 경우

long long gcd(long long a, long long b)
{
	long long q = a / b;
	long long r = a % b;

	while (r != 0) {
		a = b;
		b = r;
		q = a / b;
		r = a % b;
	}
	a = b;
	b = r;

	return a;
}

long long extended_euclid(long long m, long long a) 
{
	// a^-1 mod m
	long long mod = m;
	a %= m;
	long long q = m / a;
	long long r = m % a;
	long long t1 = 0;
	long long t2 = 1;
	long long t = (t1 - q * t2) % mod;
	if (t < 0)
		t += mod;

	while (r != 0) {
		m = a;
		a = r;
		t1 = t2;
		t2 = t;
		q = m / a;
		r = m % a;
		t = (t1 - q * t2) % mod;
		if (t < 0)
			t += mod;
	}

	t1 = t2;
	t2 = t;
	return t1 % mod;
}

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

	cin >> t;
	while (t--) {
		cin >> k >> c;

		if (k == 1 && c != 1) {
			cout << 1 << '\n';
			continue;
		}

		if (k != 1 && c == 1) {
			if ((k + 1) > 1e9) {
				cout << "IMPOSSIBLE\n";
				continue;
			}
			else {
				cout << k + 1 << '\n';
				continue;
			}
		}

		if (k == 1 && c == 1) {
			cout << 2 << '\n';
			continue;
		}

		if (gcd(k, c) != 1 || c % k == 0 || k % c == 0) {
			cout << "IMPOSSIBLE\n";
			continue;
		}

		c %= k;
		long long result = extended_euclid(k, c);
		
		if (result > 1e9) {
			cout << "IMPOSSIBLE\n";
		}
		else {
			cout << result << '\n';
		}
	}
}