파티에 K명이 참가한다. 사탕을 구입하여 K명에게 공정하게 나눠줘야한다.
그런데 한개를 잃어버리는 경우가 항상 있어서 1개를 추가 구입해야한다.
한봉지에 사탕 C개가 들어있을 때 구입해야하는 사탕 봉지 개수를 구하는 문제이다.
(단, $10^9$개 넘는 사탕 봉지는 못삼)
구입해야하는 사탕 봉지를 $y$라 하자.
그렇다면 다음과 같은 식을 유도할 수 있다.
①. $C*y=K*x+1$
양변을 K로 나누어 주면
②. $C*y%K = 1$
즉, $C*y \equiv 1$ (mod $K$)
어디서 많이 본 식이다. 그렇다.
C를 K로 나눈 나머지 연산의 곱셈에 대한 역원을 구하는 것이다.
Extended Euclidean Algorithm을 적용하면 쉽게 구할 수 있다.
C=1, K=1일때 예외처리를 잘 해주자.
#include <cstdio>
long long gcd(long long A, long long B){
if (B == 0) return A;
return gcd(B, A%B);
}
long long extended_gcd(long long A, long long B){
long long r, q, tmpA = A, t, t1 = 0, t2 = 1;
while (B != 0){
q = A / B;
r = A%B;
t = t1 - q*t2;
A = B;
B = r;
t1 = t2;
t2 = t;
}
while (t1<0) t1 += tmpA;
return t1;
}
int main(){
int T;
scanf("%d", &T);
while (T--){
long long K, C;
scanf("%lld%lld", &K, &C);
if (C == 1){ // 0 이될 수 밖에 없음
if (K + 1 > 1e9)
printf("IMPOSSIBLE\n");
else
printf("%lld\n", K + 1);
continue;
}
else if (K == 1){
printf("1\n");
continue;
}
else if (gcd(K, C) != 1){
printf("IMPOSSIBLE\n");
continue;
}
// y:우리가 구하고자하는 답, x: K*x개를 사야함
// C*y = K*x + 1
// C*y - K*x = 1 or C*y % K = 1 (단 C,K는 서로소)
long long ans = extended_gcd(K, C);
if (ans > 1e9)
printf("IMPOSSIBLE\n");
else
printf("%lld\n", ans);
}
return 0;
}
| cs |
댓글 없음:
댓글 쓰기