분수 뺄셈

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

요약
각 분수 b/n에 대해 a≥0, m>0이고 잘못된 뺄셈 (a-b)/(m-n)이 올바른 값 a/m - b/n과 같아지는 모든 a와 m을 찾아 출력한다.
난이도

보통10점 중 7점

유형
정수론, 수학, 구현, 정렬
정답자
아직 제출이 없습니다

문제

초등학교에서는 분수의 뺄셈을 배운다. 그런데 어떤 학생은 분수 뺄셈을 잘못된 방법으로 한다. 분모는 분모끼리, 분자는 분자끼리 빼는 것이다.

예를 들어 다음과 같은 분수 뺄셈이 있다고 하자.

54−912\frac{5}{4} - \frac{9}{12}

이 학생은 분모끼리 빼고 분자끼리 빼서 다음과 같이 계산한다.

54−912=5−94−12=−4−8=48=12\frac{5}{4} - \frac{9}{12} = \frac{5 - 9}{4 - 12} = \frac{-4}{-8} = \frac{4}{8} = \frac{1}{2}

그런데 신기하게도, 이 잘못된 방법의 결과가 올바른 뺄셈 결과와 같아지는 경우가 있다.

분수 bn\frac{b}{n}이 주어졌을 때, 다음 식을 만족하는 모든 aa와 mm을 찾는 프로그램을 작성하시오. 여기서 a≥0a \ge 0이고 m>0m > 0이다.

am−bn=a−bm−n\frac{a}{m} - \frac{b}{n} = \frac{a - b}{m - n}

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄로 이루어지며, 두 정수 bb와 nn이 주어진다. (1≤b,n≤1061 \le b, n \le 10^6)

입력의 마지막 줄에는 00이 두 개 주어지며, 이 줄은 처리하지 않는다.

출력

각 테스트 케이스마다 조건을 만족하는 분수를 모두 한 줄에 출력한다. 분수는 값이 작은 것부터 큰 순서로 출력하고, 값이 같은 분수가 있다면 분자가 작은 것부터 출력한다.

분수는 항상 a/m 형태로 출력하며, /의 앞과 뒤에 공백을 넣지 않는다. 한 줄에서 분수와 분수 사이에는 공백을 하나 출력한다.

예제1

  1. 예제 1

    입력
    9 12
    12 14
    4 12
    0 0
    
    예상 출력
    0/24 5/20 8/16 8/8 5/4
    0/28 9/21 9/7
    0/24 3/18 3/6