[백준] 3955번 캔디 분배 (C++)

문제

창영이는 K명의 아이들에게 캔디를 하나씩 나누어 주려고 한다. 하지만 캔디는 한 봉지에 C개가 들어있다. 따라서 창영이는 한 봉지를 사면, C개의 캔디를 가지게 된다. 아이들은 항상 한 개의 캔디를 받아야 한다. 봉지는 적어도 1개를 사야하고, 캔디는 버리면 안 된다.

K명의 아이들에게 캔디를 나누어 주기 위해서 최소 몇 봉지의 사탕을 사야하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (0 < t < 100)

각 테스트 케이스는 한 줄로 이루어져 있고, K와 C가 공백으로 구분되어 주어진다. (1 ≤ K, C ≤ 10^9)

예제 입력 1

5
10 5
10 7
1337 23
123454321 42
999999937 142857133

출력

각 테스트 케이스에 대해서 캔디를 살 수 있다면, 봉지의 수를 출력한다. 만약, 캔디를 살 수 없다면 IMPOSSIBLE을 출력한다.

예제 출력 1

IMPOSSIBLE
3
872
14696943
166666655

풀이

문제 해결 방법

이 문제는 확장 유클리드 알고리즘을 사용하여 해결할 수 있습니다. 주요 해결 단계는 다음과 같습니다:

1. 방정식 설정: Kx + 1 = Cy를 만족하는 y값을 찾아야 합니다.
2. 확장 유클리드: ax + by = gcd(a,b)의 해를 구합니다.
3. 해 검증: 구한 해가 조건을 만족하는지 확인합니다.
4. 결과 출력: 가능한 최소의 y값을 출력하거나 IMPOSSIBLE을 출력합니다.

이 알고리즘의 시간 복잡도는 O(log N)입니다.

코드

#include <stdio.h>

struct RET{
    long long x,y,g;
    RET(long long xx, long long yy, long long gg)
    {
        x = xx;
        y = yy;
        g = gg;
    };
};

long long X,K,C,Ans;

RET exgcd(long long a, long long b)
{
    // xa + by = gcd(a,b)
    if(b == 0) return RET(1,0,a); // 1*a + 0*b = a = gcd(a,b)
    long long q = a/b; // a * 1 + b * (-q) = a%b
    RET tmp = exgcd(b,a%b); // b * tmp.x + a%b * tmp.y = gcd(a,b)
    RET ret = RET(tmp.y,tmp.x-tmp.y*q,tmp.g); // a * ret.x + b * ret.y = gcd(a,b)
    return ret;     
}

long long gcd(long long a, long long b)
{
    if(b>0) return gcd(b,a%b);
    else return a;
}

RET eegcd(long long a, long long b)
{

    long long s1 = 1, s2 = 0, s3 = 0;
    long long t1 = 0, t2 = 1, t3 = 1;
    long long r1 = a, r2 = b, r3 = b, q;
    long long g = gcd(a,b) ;

    while(r3 > g)
    {
        q = r1/r2;
        r3 = r1%r2;
        s3 = s1 - q*s2;
        t3 = t1 - q*t2;
        s1 = s2; s2 = s3;
        t1 = t2; t2 = t3;
        r1 = r2;
        r2 = r3;
    }
    return RET(s3,t3,g);

}

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&K,&C);

        RET ret = eegcd(K,C);
        if(ret.g != 1) printf("IMPOSSIBLE\n");
        else 
        {
            long long ans = ret.y , ans2 = ret.x;
            while(ans <= 0||ans2 >=0) 
            {
                ans += K;
                ans2 -= C;
            }
            if(ans > 1000000000L) printf("IMPOSSIBLE\n");
            else printf("%lld\n",ans);
        }
    }
}