공정한 분배
시간 제한3초메모리 제한1024 MB
해적 수 n과 전리품 m이 주어질 때, 각 해적의 최종 몫이 정수가 되는 0과 1 사이의 분수 f 중 분모가 가장 작은 것을 구하거나 불가능하다고 판별합니다.
문제
Seven Seas를 항해하며 많은 배를 습격한 Cap'n Red와 동료 해적들이 드디어 약탈품을 나눌 준비를 마쳤다. 오랜 전통에 따라 선원들은 엄격한 해적 서열대로 원형으로 선다. Cap'n Red가 약탈품의 비율을 가져가고 나머지를 다음 해적에게 넘긴다. 다음 해적은 앞사람이 넘긴 몫의 같은 비율 를 가져가고 나머지를 또 넘긴다. 모든 해적이 같은 방식으로 남은 몫의 를 가져가고 나머지를 넘긴다. 마지막 해적은 남은 몫을 Cap'n Red에게 넘기고, Cap'n Red는 이 '공정한' 분배를 다시 시작한다. 이런 식으로 끝없이 반복된다.
여러분은 해적들에게 붙잡혔고, 적당한 비율 를 찾아야 한다. 성공하면 Cap'n Red가 목숨을 살려주겠다고 약속했다.
비율 는 보다 크고 보다 작은 유리수여야 한다. 어느 단계에서든 남은 약탈품이 로 정확히 나누어떨어질 필요는 없다. 다만 이 과정을 무한히 진행했을 때 각 해적이 받는 약탈품의 총량은 정수여야 한다.
입력
입력은 한 줄이며, 두 정수 과 이 주어진다. ()은 Cap'n Red를 포함한 해적의 수이고, ()은 약탈품의 총 가치이다.
출력
위에서 설명한 대로 를 만족하는 두 양의 정수 와 를 한 줄에 출력한다. 조건을 만족하는 분수가 여러 개면 가 가장 작은 것을 고르고, 도 같다면 가 가장 작은 것을 고른다. 조건을 만족하는 분수가 없으면 impossible을 출력한다.