만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

이차식의 인수분해

면접 대비

시간 제한1초메모리 제한1024 MB

요약
정수 a, b, c가 주어진 이차식 ax^2 + bx + c를 (px + q)(rx + s) 꼴의 두 일차식 곱으로 나타내는 정수 p, q, r, s를 찾습니다. 불가능하면 Impossible을 출력합니다.
난이도

보통10점 중 4점

유형
수학, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

대수학 과정의 첫 단계에서 학생들은 이차식과 그 인수분해를 배운다. 인수분해는 많은 학생에게 큰 부담이 된다. 인수분해를 익히지 못한 학생이 많아, 그들은 고급 대수학의 아름다움을 알 기회를 얻지 못한다. 인수분해가 오히려 수학을 싫어하는 사람을 늘리기도 한다.

이 문제에서는 대수학 수강생을 돕는 프로그램을 작성한다. 주어진 이차식이 두 일차식의 곱으로 인수분해되는지 판단하고, 가능하면 그 방법을 찾는다. 이 문제의 모든 계수는 정수다.

이차식 ax2+bx+cax^2 + bx + c의 계수 aa, bb, cc가 주어진다. 세 값은 절댓값이 10000 이하인 정수다. 프로그램은 ax2+bx+c=(px+q)(rx+s)ax^2 + bx + c = (px + q)(rx + s)를 만족하는 정수 pp, qq, rr, ss를 찾아야 한다. 정수 계수로는 인수분해할 수 없는 식도 있으며, 그 경우 인수분해가 불가능하다고 보고해야 한다.

입력

입력은 이차식 하나를 나타내는 줄들의 연속이다. 각 줄의 형식은 다음과 같다.

aa bb cc

aa, bb, cc는 공백으로 구분된 정수이며, 다음 부등식을 만족한다.

0<a≤100000 \lt a \le 10000

−10000≤b≤10000-10000 \le b \le 10000

−10000≤c≤10000-10000 \le c \le 10000

aa, bb, cc의 최대공약수는 1이다. 세 값을 모두 나누는 1보다 큰 정수 kk는 없다.

입력의 끝은 0 세 개로 이루어진 줄로 표시된다.

출력

입력의 각 줄에 대해, 인수분해가 존재하면 정수 pp, qq, rr, ss를 이 순서대로 한 줄에 출력한다. 정수 사이는 공백 하나 이상으로 구분한다. 인수분해가 불가능하면 "Impossible"이라는 단어만 출력한다.

네 계수는 다음 조건을 만족해야 한다.

p>0p > 0

r>0r > 0

p>rp > r이거나, p=rp = r이고 q≥sq \ge s이다.

이 조건과 aa, bb, cc의 최대공약수가 1이라는 사실 때문에 답은 하나로 정해진다. 인수분해를 하나 찾았다면 다른 방법을 찾을 필요는 없다.

예제1

  1. 예제 1

    입력
    2 5 2
    1 1 1
    10 -7 0
    1 0 -3
    0 0 0
    
    예상 출력
    2 1 1 2
    Impossible
    10 -7 1 0
    Impossible