문제에서 요구하는 사항을 정리해보면, 사탕이 C개 들어있는 사탕 봉지를 구입하여 모두에게 골고루 나누어주고, 사탕 1개를 남겨놔야 될 때 구매할 수 있는 경우 중 하나를 출력하면 되는 문제이다. 즉, $(C * x) % K = 1$ 을 성립해야 하므로 이는 $xC\equiv 1\pmod K$ 를 만족하는 x를 찾으면 된다.
이 문제에서는 코너 케이스로 해결해 주어야 할 부분이 먼저 있다. 1번째로 사탕이 1봉지에 1개만 들어있을 때는 항상 C+1 개 만큼의 사탕봉지를 구입해야 함이 자명하다. 단, 10억개를 넘으면 안되므로 이를 또 체크해 준다. 사탕이 1봉지에 2개 이상 들어있고 사람이 1명일 때는 1봉지만 구입하면 되는 것도 자명하다. 1개만 남겨놓고 전부 주면 되기 때문이다.
이제 나머지 경우를 보자. 항상 1개를 남겨야 하므로 gcd(K,C)가 1이 아닐 경우에는 문제를 풀 수 없음을 알 수 있다. 즉, K와 C는 항상 서로소이므로 위의 합동식은 항상 유일한 해를 가지게 된다. 이제 앞에서 본 개념대로 확장 유클리디안 알고리즘을 이용하여 필요한 값을 구한다. 해를 구한 뒤 해를 만족하는 값을 출력해줄 때, 음수가 출력되지 않도록 별도의 처리를 해줄 필요가 있다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) { return !b ? a : gcd(b, a%b); }
int main()
{
int n;
ll a, b;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a >> b;
if (b == 1) {
if(a+1>1e9) cout << "IMPOSSIBLE\n";
else cout << a + 1 << "\n";
continue;
}
if (a == 1) {
cout << "1\n";
continue;
}
if (gcd(a, b) != 1) {
cout << "IMPOSSIBLE\n";
continue;
}
ll x[2] = { 1,0 }, y[2] = { 0,1 }, z[2] = { a,b }, q;
while (z[1]!=1) {
ll nq = z[0] / z[1], nz = z[0] % z[1];
ll nx = x[0] - (x[1] * nq), ny = y[0] - (y[1] * nq);
x[0] = x[1], x[1] = nx;
y[0] = y[1], y[1] = ny;
z[0] = z[1], z[1] = nz;
}
while (y[1] < 0) {
y[1] += a;
}
if (y[1] > 1e9) cout << "IMPOSSIBLE\n";
else cout << y[1] << "\n";
}
}