3955번: Candy Distribution

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


cy - kx = 1 (10^9>=y>=0, x>=1, y, x는 정수)을 만족하는 y를 구하는 문제
간단하게 확장 유클리드 알고리즘으로 풀 수 있다.
gcd(c,k) = d라고 하면 d=1이면 해가 존재하며 그 이외에는 해가 없다.

확장 유클리드 알고리즘으로 구한 특수해가 (x,y) = (x0, y0)라고 하면
일반해는 (x0+ct, y0+kt)로 나타낼 수 있다.
참고로 이 알고리즘을 통해 나온 특수해 (x0,y0)는 abs(x0) <= c/d * (1/d) = c, abs(y0) <= k/d * (1/d) = k 임이 보장되어있다.

테스트케이스마다 시간복잡도 $O(\lg(min(c,k)))$

#include<cstdio>
int f(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1 / a;
        y = 0;
        return a;
    }
    int ret = f(b, a%b, y, x);
    y -= a / b*x;
    return ret;
}
int t, k, c;
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d", &k, &c);
        int x, y, ret = f(c, -k, x, y);
        while (y <= 0) x += k, y += c;
        ret > 1 || ret < -1 || x > 1e9 ? puts("IMPOSSIBLE") : printf("%d\n", x);
    }
    return 0;
}