3955번: 캔디 분배 - 수학(확장 유클리드 호제법)

확장 유클리드 호제법 응용 문제.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

pll EUC(ll K, ll C)
{
    if(C == 0) return {1, 0};
    auto [x, y] = EUC(C, K%C);
    return {y, x - K/C * y};
}

void solve()
{
    ll K, C; cin >> K >> C;
    
    if(gcd(K, C) != 1)
    {
        cout << "IMPOSSIBLE\n";
        return;
    }
    
    auto [x, y] = EUC(K, C); //x, y : 방정식을 만족하는 해 중 하나
    
    //zx, zy : x, y의 일반해
    //zx = x + z*C, zy = y - z*K
    ll zx = -x>0 ? (-x-1)/C+1 : (-x)/C; //x < 0
    ll zy = y>0 ? (y-1)/K+1 : y/K; //y > 0
    ll z = min(zx, zy) - 1; //x < 0, y > 0을 만족시키는 z
    
    if(y-ll(1e9) <= z*K) cout << y-z*K << "\n"; //y <= 1e9을 만족시키는 z를 구하고, 최종적으로 y를 구한다.
    else cout << "IMPOSSIBLE\n";
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    int t; cin >> t;
    while(t--) solve();
}