2020 C Chapter 7 - C의 제어문: 분기와 점프

• Problem
• Standing
• Statistics
• Status
• Discuss

C - 디오판토스 방정식

• Submit
• Status
• Discuss
• Summary

Description

주어진 a, b, d에 대해 a × x + b × y = d이며 x>0을 만족하는 정수해 x, y 중 x가 가장 작은 경우를 찾아보자.

Input

* Line 1 : 입력의 갯수 N이 주어진다. (1≤N≤100)

* Line 2~N+1 : a, b, d가 공백으로 구분되어 주어진다. (-20000 ≤ a, b, d ≤ 20000, b ≠ 0)

Output

* Line 1~N : a × x + b × y = d이며 x>0인 정수해 x, y 쌍 중 x가 가장 작은 x, y 쌍을 출력한다. 만약 만족하는 x, y가 없다면 IMPOSSIBLE를 출력한다.

Sample Input

3
3 5 1
2 2 3
2 3 -3

Sample Output

(2, -1)
IMPOSSIBLE
(3, -3)