시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 510 69 45 14.286%

문제

초등학교에서 학생들은 분수 뺄셈을 하는 법을 배운다. 하지만, 상근이는 분수 뺄셈을 아직도 제대로 하는 법을 모른다.

예를 들어, 아래와 같은 분수 뺄셈이 있다.

상근이는 분모 끼리 빼고, 분자 끼리 빼는 방법으로 뺄셈을 한다. 아래 그림을 보자.

그런데, 신기하게도 이 방법이 실제 결과와 같은 경우가 있다.

분수 b/n이 주어진다. 이 때, 아래 식을 만족하는 모든 a와 m을 찾는 프로그램을 작성하시오. (a ≥ 0, m > 0)

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, b와 n이 주어진다. (1 ≤ b, n ≤ 106) 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 문제의 조건을 만족하는 분수를 작은 것부터 크기 순서대로 모두 출력한다. 출력하고자 하는 분수의 크기가 같은 경우에는 분자의 크기가 작은 것 부터 출력한다. 분수는 항상 a/m 형태로 출력해야 하며, /의 앞과 뒤에 공백을 출력하면 안된다. 분수와 분수 사이에는 공백을 하나 출력한다.

예제 입력 1

9 12
12 14
4 12
0 0

예제 출력 1

0/24 5/20 8/16 8/8 5/4
0/28 9/21 9/7
0/24 3/18 3/6

힌트

W3sicHJvYmxlbV9pZCI6IjQ3ODIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODRcdWMyMTggXHViZTg0XHVjMTQ4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWNkMDhcdWI0ZjFcdWQ1NTlcdWFkNTBcdWM1ZDBcdWMxMWMgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YmQ4NFx1YzIxOCBcdWJlODRcdWMxNDhcdWM3NDQgXHVkNTU4XHViMjk0IFx1YmM5NVx1Yzc0NCBcdWJjMzBcdWM2YjRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YmQ4NFx1YzIxOCBcdWJlODRcdWMxNDhcdWM3NDQgXHVjNTQ0XHVjOWMxXHViM2M0IFx1YzgxY1x1YjMwMFx1Yjg1YyBcdWQ1NThcdWIyOTQgXHViYzk1XHVjNzQ0IFx1YmFhOFx1Yjk3OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWJkODRcdWMyMTggXHViZTg0XHVjMTQ4XHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9mcmFjMS5wbmdcIiBzdHlsZT1cImhlaWdodDo2MHB4OyB3aWR0aDo5NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJkODRcdWJhYTggXHViMDdjXHViOWFjIFx1YmU3Y1x1YWNlMCwgXHViZDg0XHVjNzkwIFx1YjA3Y1x1YjlhYyBcdWJlN2NcdWIyOTQgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YmU4NFx1YzE0OFx1Yzc0NCBcdWQ1NWNcdWIyZTQuIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDQgXHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2ZyYWMyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjYwcHg7IHdpZHRoOjI0NXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjdmMFx1YjM3MCwgXHVjMmUwXHVhZTMwXHVkNTU4XHVhYzhjXHViM2M0IFx1Yzc3NCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjMmU0XHVjODFjIFx1YWNiMFx1YWNmY1x1YzY0MCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViZDg0XHVjMjE4IGJcL25cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWM1NDRcdWI3OTggXHVjMmRkXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWJhYThcdWI0ZTAgYVx1YzY0MCBtXHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiAoYSAmZ2U7IDAsIG0gJmd0OyAwKTxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2ZyYWMzLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjYwcHg7IHdpZHRoOjE2MXB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgYlx1YzY0MCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBiLCBuICZsZTsgMTA8c3VwPjY8XC9zdXA+KSBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YjQ1MCBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViZDg0XHVjMjE4XHViOTdjIFx1Yzc5MVx1Yzc0MCBcdWFjODNcdWJkODBcdWQxMzAgXHVkMDZjXHVhZTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWJhYThcdWI0NTAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IFx1YmQ4NFx1YzIxOFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWJkODRcdWM3OTBcdWM3NTggXHVkMDZjXHVhZTMwXHVhYzAwIFx1Yzc5MVx1Yzc0MCBcdWFjODMgXHViZDgwXHVkMTMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViZDg0XHVjMjE4XHViMjk0IFx1ZDU2ZFx1YzBjMSBhXC9tIFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTU4XHViYTcwLCBcL1x1Yzc1OCBcdWM1NWVcdWFjZmMgXHViNGE0XHVjNWQwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQmbmJzcDtcdWM1NDhcdWI0MWNcdWIyZTQuIFx1YmQ4NFx1YzIxOFx1YzY0MCBcdWJkODRcdWMyMTggXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ3ODIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJEbyBJdCBXcm9uZywgR2V0IEl0IFJpZ2h0IiwiZGVzY3JpcHRpb24iOiI8cD5JbiBlbGVtZW50YXJ5IHNjaG9vbCwgc3R1ZGVudHMgbGVhcm4gdG8gc3VidHJhY3QgZnJhY3Rpb25zIGJ5IGZpcnN0IGdldHRpbmcgYSBjb21tb24gZGVub21pbmF0b3IgYW5kIHRoZW4gc3VidHJhY3RpbmcgdGhlIG51bWVyYXRvcnMuIEhvd2V2ZXIsIHNvbWV0aW1lcyBhIHN0dWRlbnQgd2lsbCB3b3JrIHRoZSBwcm9ibGVtIGluY29ycmVjdGx5IGFuZCBzdGlsbCBhcnJpdmUgYXQgdGhlIGNvcnJlY3QgYW5zd2VyLiBGb3IgZXhhbXBsZSwgZm9yIHRoZSBwcm9ibGVtPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZnJhYzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NjBweDsgd2lkdGg6OTRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5vbmUgY2FuIHN1YnRyYWN0IHRoZSBudW1iZXJzIGluIHRoZSBudW1lcmF0b3IgYW5kIHRoZW4gc3VidHJhY3QgdGhlIG51bWJlcnMgaW4gdGhlIGRlbm9taW5hdG9yLCBzaW1wbGlmeSBhbmQgZ2V0IHRoZSBhbnN3ZXIuIGkuZS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9mcmFjMi5wbmdcIiBzdHlsZT1cImhlaWdodDo2MHB4OyB3aWR0aDoyNDVweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Gb3IgYSBnaXZlbiBmcmFjdGlvbiBiXC9uLCB5b3VyIHRhc2sgaXMgdG8gZmluZCBhbGwgb2YgdGhlIHZhbHVlcyBhIGFuZCBtLCB3aGVyZSBhJmdlOzAgYW5kIG0mZ3Q7MCwgZm9yIHdoaWNoPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZnJhYzMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NjBweDsgd2lkdGg6MTYxcHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZXJlIHdpbGwgYmUgc2V2ZXJhbCB0ZXN0IGNhc2VzIGluIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugd2lsbCBjb25zaXN0IG9mIGEgc2luZ2xlIGxpbmUgd2l0aCB0d28gaW50ZWdlcnMsIGIgYW5kIG4gKDEmbGU7YixuJmxlOzEwPHN1cD42PFwvc3VwPikgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiBUaGUgaW5wdXQgd2lsbCBlbmQgd2l0aCBhIGxpbmUgd2l0aCB0d28gMHMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggY2FzZSwgb3V0cHV0IGFsbCBvZiB0aGUgcmVxdWVzdGVkIGZyYWN0aW9ucyBvbiBhIHNpbmdsZSBsaW5lLCBzb3J0ZWQgZnJvbSBzbWFsbGVzdCB0byBsYXJnZXN0LiBGb3IgZXF1aXZhbGVudCBmcmFjdGlvbnMsIHByaW50IHRoZSBvbmUgd2l0aCB0aGUgc21hbGxlciBudW1lcmF0b3IgZmlyc3QuIE91dHB1dCBlYWNoIGZyYWN0aW9uIGluIHRoZSBmb3JtICZsZHF1bzthXC9tJnJkcXVvOyB3aXRoIG5vIHNwYWNlcyBpbW1lZGlhdGVseSBiZWZvcmUgb3IgYWZ0ZXIgdGhlICZsZHF1bztcLyZyZHF1bzsuIE91dHB1dCBhIHNpbmdsZSBzcGFjZSBiZXR3ZWVuIGZyYWN0aW9ucy4gT3V0cHV0IG5vIGV4dHJhIHNwYWNlcywgYW5kIGRvIG5vdCBzZXBhcmF0ZSBhbnN3ZXJzIHdpdGggYmxhbmsgbGluZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d