(3955) 캔디 분배

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

단계별로 풀어보기

45단계(수학 2) 1번째

 

 

 

구매하려는 사탕 개수를 Y라고 하면 Y*C=K*X+1이다.

따라서 aX+bY에서 a=-K, b=C로 두고 확장 유클리드 알고리즘을 쓰면 된다.

 

코드에서 루프가 끝난 뒤 r.first는 -K와 C의 최대공약수, s.first와 t.first는 X와 Y의 특수해이다.

-K와 C의 최대공약수가 1이 아니라면 정수해가 없으므로 불가능하고,

최대공약수가 음수라면 계산 편의를 위해 전부 양수로 바꾸어준다.

문제의 특성을 생각하면 X(나눠주는 사탕)와 Y(구매하는 사탕 봉지)는 10^9 이하의 양수가 되어야 한다.

이때 X와 Y의 일반해는 X'=X+nC, Y'=Y+nK이다. n의 값을 적절히 조절해 해가 유효 범위 내 들어올 수 있도록 하고, 할 수 없다면 불가능을 출력한다.

 

 

 

#include <iostream>
using namespace std;
#define MAX 1000000000

void solve(){
  long k, c;
  
  cin >> k >> c;
  
  long q;
  pair<long, long> r= {-k, c};
  pair<long, long> s= {1, 0};
  pair<long, long> t= {0, 1};
  
  while(r.second){
    q= r.first/r.second;
    r= {r.second, r.first-r.second*q};
    s= {s.second, s.first-s.second*q};
    t= {t.second, t.first-t.second*q};
  }
  
  if(abs(r.first)!=1){
    cout << "IMPOSSIBLE\n";
    return;
  }

  if(r.first==-1){
    s.first*= -1;
    t.first*= -1;
  }

  if(s.first>0){
    long n= min((s.first-1)/c, (t.first-1)/k);
    if(MAX<t.first-n*k){
      cout << "IMPOSSIBLE\n";
    }else{
      cout << t.first-n*k << "\n";
    }
  }else{
    long n= max((-s.first)/c, (-t.first)/k)+1;
    if(MAX<t.first+n*k){
      cout << "IMPOSSIBLE\n";
    }else{
      cout << t.first+n*k << "\n";
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    solve();
  }
  
  return 0;
}