[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 3955번 _ 캔디 분배

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

3955번: 캔디 분배

[문제]

창영이는 선영이가 사탕을 공평하게 나누어주지 않으면 친구들을 때릴정도로 사탕을 좋아한다.

따라서, 선영이는 다음 파티에 사용할 사탕을 구매하기 전에 고민을 하기 시작했다.

만약 파티에 K명이 참가한다면, 공정하게 나누어주려면 K×X개를 사야 한다. (X는 자연수) 

선영이는 항상 적어도 한 아이는 사탕을 잃어버린다는 사실을 알고 있다. 그래서 캔디를 하나 더 구매해 총 (K×X+1)개를 구매하려고 한다.

사탕은 봉지 단위로 판매한다. 한 봉지에는 사탕이 총 C개 들어있다. 문제의 조건을 만족하면서 구매할 수 있는 사탕 봉지의 개수를 구하는 프로그램을 작성하시오.

 

[입력]

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (0 < t < 100) 각 테스트 케이스는 한 줄로 이루어져 있고, K와 C가 공백으로 구분되어져서 주어진다. (1 ≤ K, C ≤ 109) 선영이는 부자가 아니기 때문에 10**9개를 넘는 사탕 봉지를 구매하지 못한다.

[출력]

각 테스트 케이스에 대해서 문제의 조건을 만족시키면서 구매할 수 있는 사탕 봉지가 없다면, "IMPOSSIBLE"을 출력한다. 이 경우가 아닌 경우에는 선영이가 구매해야 하는 사탕 봉지의 수를 출력한다. 만약, 가능한 봉지의 수가 여러개라면 아무거나 출력한다.

 

[아이디어]

1) modulo 역을 구하는 연산을 pow() 함수를 이용해 할 수 있다.

(pow(역을 찾는 대상, 기준 숫자-2(또는 -1), 기준 숫자))

2) k 또는 c가 0인 경우에 대해 예외 처리를 해주어야 한다.

 

for _ in range(int(input())):
    a,b = map(int,input().split())
    if a==1:
        print(1 if b>1 else 2)
    elif b==1:
        print(a+1 if a!=int(1e9) else "IMPOSSIBLE")
    else:
        try:
            tmp = pow(b, -1, a)
            print(tmp if tmp<=int(1e9) else "IMPOSSIBLE")
        except:
            print("IMPOSSIBLE")