캔디 분배 - 3955

//3955 - 캔디 분배
 
#include <iostream>
using namespace std;
 
#define MOD 1000000001
 
int N, K;
 
pair<int, int> EEA(int a, int b)
{
    long long old_r, r, temp_r;
    long long old_s, s, temp_s;
    long long old_t, t, temp_t;
    long long q;
    old_r = a, r = b;
    old_s = 1, s = 0;
    old_t = 0, t = 1;
 
    while (r)
    {
        q = old_r / r;
 
        temp_r = r;
        r = old_r - r * q;
        old_r = temp_r;
 
        temp_s = s;
        s = old_s - s * q;
        old_s = temp_s;
 
        temp_t = t;
        t = old_t - t * q;
        old_t = temp_t;
    }
    if (old_r != 1)
        return make_pair(2, 0);
    else
    {
        while (old_s < 0)
            old_s += b;
        return make_pair(1, old_s);
    }
}
 
int main()
{
    int C;
    cin >> C;
    for (int tn = 0; tn < C; ++tn)
    {
        cin >> N >> K;
 
        pair<int, int> p = EEA(K, N);
        if (p.first != 1)
            cout << "IMPOSSIBLE"
                 << "\n";
        else
        {
            long long ans = p.second;
            while(K*ans < N+1)
                ans += N;
            if(ans < MOD)
                cout << ans << "\n";
            else cout << "IMPOSSIBLE\n";
        }
    }
}

 

 

 

 

 

 

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

3955번: 캔디 분배

 

 

 

 

 

 

캔디 분배

주어진 문제의 조건을 식으로 나타내면

Cx = Ky + 1 입니다.(x는 사탕 봉지 개수, y는 한사람에게 나눠줄 사탕의 개수)

위의 식은

Cx - Ky = 1 로 바꿀수 있고, 또한 Cx + Ky = 1로 도 나타낼수 있습니다.

K는  자연수이기 때문에 양변에 mod K를 해주게 되면

Cx = 1 (mod K) 라는 식을 완성할 수 있습니다.

저희는 K modular계에서 C의 곱셈에 대한 역원을 찾은 다음, 해당 역원이 될수 있는 일반 자연수에서 의 후보중 문제 조건을 만족하는 것 하나를 고르면 됩니다.

 

Cx = 1 (mod K) 에서의 C에 대한 곱셈의 역원 x는 확장 유클리드 알고리즘으로 쉽게 구할 수 있습니다.

 

구해진 x는 modular K계 안의 숫자이니, (즉 x 는 0 <= x < K 입니다. 여기서 x가 만약 1이 된다면 실제로 x가 될수 있는 값들은 자연수 범위에서 {1, K+1, 2*K + 1 ....} 가 됩니다.)

문제의 조건에 맞는 수가 나올때까지 K를 계속 더해주면서 찾아 주면 됩니다. 10^9를 넘어가게 되면 impossible을 출력합니다.