시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 550 90 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+XHViZDg0XHVjMjE4IGJcL25cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzU0NFx1Yjc5OCBcdWMyZGRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YmFhOFx1YjRlMCBhXHVjNjQwIG1cdWM3NDQgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIChhICZnZTsgMCwgbSAmZ3Q7IDApPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZnJhYzMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NjBweDsgd2lkdGg6MTYxcHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBiXHVjNjQwIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IGIsIG4gJmxlOyAxMDxzdXA+NjxcL3N1cD4pIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWJkODRcdWMyMThcdWI5N2MgXHVjNzkxXHVjNzQwIFx1YWM4M1x1YmQ4MFx1ZDEzMCBcdWQwNmNcdWFlMzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YmFhOFx1YjQ1MCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMFx1Yzc5MCBcdWQ1NThcdWIyOTQgXHViZDg0XHVjMjE4XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YmQ4NFx1Yzc5MFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgXHVjNzkxXHVjNzQwIFx1YWM4MyBcdWJkODBcdWQxMzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJkODRcdWMyMThcdWIyOTQgXHVkNTZkXHVjMGMxIGFcL20gXHVkNjE1XHVkMGRjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWJhNzAsIFwvXHVjNzU4IFx1YzU1ZVx1YWNmYyBcdWI0YTRcdWM1ZDAgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCZuYnNwO1x1YzU0OFx1YjQxY1x1YjJlNC4gXHViZDg0XHVjMjE4XHVjNjQwIFx1YmQ4NFx1YzIxOCBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDc4MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRvIEl0IFdyb25nLCBHZXQgSXQgUmlnaHQiLCJkZXNjcmlwdGlvbiI6IjxwPkluIGVsZW1lbnRhcnkgc2Nob29sLCBzdHVkZW50cyBsZWFybiB0byBzdWJ0cmFjdCBmcmFjdGlvbnMgYnkgZmlyc3QgZ2V0dGluZyBhIGNvbW1vbiBkZW5vbWluYXRvciBhbmQgdGhlbiBzdWJ0cmFjdGluZyB0aGUgbnVtZXJhdG9ycy4gSG93ZXZlciwgc29tZXRpbWVzIGEgc3R1ZGVudCB3aWxsIHdvcmsgdGhlIHByb2JsZW0gaW5jb3JyZWN0bHkgYW5kIHN0aWxsIGFycml2ZSBhdCB0aGUgY29ycmVjdCBhbnN3ZXIuIEZvciBleGFtcGxlLCBmb3IgdGhlIHByb2JsZW08XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9mcmFjMS5wbmdcIiBzdHlsZT1cImhlaWdodDo2MHB4OyB3aWR0aDo5NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPm9uZSBjYW4gc3VidHJhY3QgdGhlIG51bWJlcnMgaW4gdGhlIG51bWVyYXRvciBhbmQgdGhlbiBzdWJ0cmFjdCB0aGUgbnVtYmVycyBpbiB0aGUgZGVub21pbmF0b3IsIHNpbXBsaWZ5IGFuZCBnZXQgdGhlIGFuc3dlci4gaS5lLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2ZyYWMyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjYwcHg7IHdpZHRoOjI0NXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZvciBhIGdpdmVuIGZyYWN0aW9uIGJcL24sIHlvdXIgdGFzayBpcyB0byBmaW5kIGFsbCBvZiB0aGUgdmFsdWVzIGEgYW5kIG0sIHdoZXJlIGEmZ2U7MCBhbmQgbSZndDswLCBmb3Igd2hpY2g8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9mcmFjMy5wbmdcIiBzdHlsZT1cImhlaWdodDo2MHB4OyB3aWR0aDoxNjFweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgd2lsbCBiZSBzZXZlcmFsIHRlc3QgY2FzZXMgaW4gdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSB3aWxsIGNvbnNpc3Qgb2YgYSBzaW5nbGUgbGluZSB3aXRoIHR3byBpbnRlZ2VycywgYiBhbmQgbiAoMSZsZTtiLG4mbGU7MTA8c3VwPjY8XC9zdXA+KSBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIFRoZSBpbnB1dCB3aWxsIGVuZCB3aXRoIGEgbGluZSB3aXRoIHR3byAwcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBjYXNlLCBvdXRwdXQgYWxsIG9mIHRoZSByZXF1ZXN0ZWQgZnJhY3Rpb25zIG9uIGEgc2luZ2xlIGxpbmUsIHNvcnRlZCBmcm9tIHNtYWxsZXN0IHRvIGxhcmdlc3QuIEZvciBlcXVpdmFsZW50IGZyYWN0aW9ucywgcHJpbnQgdGhlIG9uZSB3aXRoIHRoZSBzbWFsbGVyIG51bWVyYXRvciBmaXJzdC4gT3V0cHV0IGVhY2ggZnJhY3Rpb24gaW4gdGhlIGZvcm0gJmxkcXVvO2FcL20mcmRxdW87IHdpdGggbm8gc3BhY2VzIGltbWVkaWF0ZWx5IGJlZm9yZSBvciBhZnRlciB0aGUgJmxkcXVvO1wvJnJkcXVvOy4gT3V0cHV0IGEgc2luZ2xlIHNwYWNlIGJldHdlZW4gZnJhY3Rpb25zLiBPdXRwdXQgbm8gZXh0cmEgc3BhY2VzLCBhbmQgZG8gbm90IHNlcGFyYXRlIGFuc3dlcnMgd2l0aCBibGFuayBsaW5lcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=