시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1596 588 496 43.281%

문제

선영이의 직업은 소시지 요리사이다. 소시지를 팔기 전에 음식 평론가 M명을 모아서 맛을 테스트해보려고 한다.

선영이는 동일한 소시지를 총 N개를 준비했다. 이 소시지를 모든 평론가들이 같은 양을 받게 소시지를 자르려고 한다. 이때, 소시지를 자르는 횟수를 최소로 하려고 한다.

예를 들어, 소시지가 2개, 평론가가 6명있는 경우를 생각해보자. 이때, 각 소시지를 세 조각으로 만든 다음, 각 평론가에게 한 조각씩 주면 된다. 이 경우에 소시지는 총 네 번 자르게 된다. 다른 경우로 소시지가 3개, 평론가가 4명 있는 경우를 생각해보자. 이때는 각 소시지의 크기를 3:1로 잘라서 큰 조각을 평론가에게 하나씩 주고, 남은 조각을 평론가에게 주면 모두 동일한 양을 받게 된다.

소시지의 수와 평론가의 수가 주어졌을 때, 모든 평론가에게 같은 양의 소시지를 주기 위해 필요한 칼질의 수를 구하는 프로그램을 작성하시오. 

입력

첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100)

출력

첫째 줄에 모든 평론가에게 동일한 양을 주기 위해 필요한 칼질 횟수의 최솟값을 출력한다. 

예제 입력 1

2 6

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjExODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NGNcdWMyZGQgXHVkM2M5XHViODYwXHVhYzAwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWM3NTggXHVjOWMxXHVjNWM1XHVjNzQwIFx1YzE4Y1x1YzJkY1x1YzljMCBcdWM2OTRcdWI5YWNcdWMwYWNcdWM3NzRcdWIyZTQuIFx1YzE4Y1x1YzJkY1x1YzljMFx1Yjk3YyBcdWQzMTRcdWFlMzAgXHVjODA0XHVjNWQwIFx1Yzc0Y1x1YzJkZCBcdWQzYzlcdWI4NjBcdWFjMDAgTVx1YmE4NVx1Yzc0NCBcdWJhYThcdWM1NDRcdWMxMWMgXHViOWRiXHVjNzQ0IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1ZDU3NFx1YmNmNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWIzZDlcdWM3N2NcdWQ1NWMgXHVjMThjXHVjMmRjXHVjOWMwXHViOTdjIFx1Y2QxZCBOXHVhYzFjXHViOTdjIFx1YzkwMFx1YmU0NFx1ZDU4OFx1YjJlNC4gXHVjNzc0IFx1YzE4Y1x1YzJkY1x1YzljMFx1Yjk3YyBcdWJhYThcdWI0ZTAgXHVkM2M5XHViODYwXHVhYzAwXHViNGU0XHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWM1OTFcdWM3NDQgXHViYzFiXHVhYzhjIFx1YzE4Y1x1YzJkY1x1YzljMFx1Yjk3YyBcdWM3OTBcdWI5NzRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzE4Y1x1YzJkY1x1YzljMFx1Yjk3YyBcdWM3OTBcdWI5NzRcdWIyOTQgXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWMxOGNcdWMyZGNcdWM5YzBcdWFjMDAgMlx1YWMxYywgXHVkM2M5XHViODYwXHVhYzAwXHVhYzAwIDZcdWJhODVcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MC4gXHVjNzc0XHViNTRjLCBcdWFjMDEgXHVjMThjXHVjMmRjXHVjOWMwXHViOTdjIFx1YzEzOCBcdWM4NzBcdWFjMDFcdWM3M2NcdWI4NWMgXHViOWNjXHViNGUwIFx1YjJlNFx1Yzc0YywgXHVhYzAxIFx1ZDNjOVx1Yjg2MFx1YWMwMFx1YzVkMFx1YWM4YyBcdWQ1NWMgXHVjODcwXHVhYzAxXHVjNTI5IFx1YzhmY1x1YmE3NCBcdWI0MWNcdWIyZTQuIFx1Yzc3NCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVjMThjXHVjMmRjXHVjOWMwXHViMjk0IFx1Y2QxZCBcdWIxMjQgXHViYzg4IFx1Yzc5MFx1Yjk3NFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjJlNFx1Yjk3OCBcdWFjYmRcdWM2YjBcdWI4NWMgXHVjMThjXHVjMmRjXHVjOWMwXHVhYzAwIDNcdWFjMWMsIFx1ZDNjOVx1Yjg2MFx1YWMwMFx1YWMwMCA0XHViYTg1IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5N2MgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwLiBcdWM3NzRcdWI1NGNcdWIyOTQgXHVhYzAxIFx1YzE4Y1x1YzJkY1x1YzljMFx1Yzc1OCZuYnNwO1x1ZDA2Y1x1YWUzMFx1Yjk3YyZuYnNwOzM6MVx1Yjg1YyBcdWM3OThcdWI3N2NcdWMxMWMgXHVkMDcwIFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWQzYzlcdWI4NjBcdWFjMDBcdWM1ZDBcdWFjOGMgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YWNlMCwgXHViMGE4XHVjNzQwIFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWQzYzlcdWI4NjBcdWFjMDBcdWM1ZDBcdWFjOGMgXHVjOGZjXHViYTc0IFx1YmFhOFx1YjQ1MCBcdWIzZDlcdWM3N2NcdWQ1NWMgXHVjNTkxXHVjNzQ0IFx1YmMxYlx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzE4Y1x1YzJkY1x1YzljMFx1Yzc1OCBcdWMyMThcdWM2NDAgXHVkM2M5XHViODYwXHVhYzAwXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHVkM2M5XHViODYwXHVhYzAwXHVjNWQwXHVhYzhjIFx1YWMxOVx1Yzc0MCBcdWM1OTFcdWM3NTggXHVjMThjXHVjMmRjXHVjOWMwXHViOTdjIFx1YzhmY1x1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2U3Y1x1YzljOFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzE4Y1x1YzJkY1x1YzljMFx1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWQzYzlcdWI4NjBcdWFjMDBcdWM3NTggXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4sIE0gJmxlOyAxMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJhYThcdWI0ZTAgXHVkM2M5XHViODYwXHVhYzAwXHVjNWQwXHVhYzhjIFx1YjNkOVx1Yzc3Y1x1ZDU1YyBcdWM1OTFcdWM3NDQgXHVjOGZjXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZTdjXHVjOWM4IFx1ZDY5Zlx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExODgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLVVx1MDE2MEFcdTAxMGMiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGhhcyBnaXZlbiB1cCBvbiB0aGUgZGlmZmljdWx0IGNvYWNoIGpvYiBhbmQgc3dpdGNoZWQgdG8gZm9vZCB0YXN0aW5nIGluc3RlYWQuIEhhdmluZyBza2lwcGVkIGJyZWFrZmFzdCBsaWtlIGEgcHJvZmVzc2lvbmFsIGNvbm5vaXNzZXVyLCBoZSBpcyB2aXNpdGluZyBhIENyb2F0aWFuIGN1cmVkIG1lYXQgZmVzdGl2YWwuIFRoZSBtb3N0IHJlbm93bmVkIGNvb2sgYXQgdGhlIGZlc3RpdmFsLCBNYXJpamFuIEJhanMsIGhhcyBwcmVwYXJlZCBOIGVxdWFsIHNhdXNhZ2VzIHdoaWNoIG5lZWQgdG8gYmUgZGlzdHJpYnV0ZWQgdG8gTSB0YXN0ZXJzIHN1Y2ggdGhhdCBlYWNoIHRhc3RlciBnZXRzIGEgcHJlY2lzZWx5IGVxdWFsIGFtb3VudC4gSGUgd2lsbCB1c2UgaGlzIHRydXN0ZWQga25pZmUgdG8gY3V0IHRoZW0gaW50byBwaWVjZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIG9yZGVyIHRvIGVsZWdhbnRseSBkaXZpZGUgdGhlIHNhdXNhZ2VzLCB0aGUgbnVtYmVyIG9mIGN1dHMgc3BsaXR0aW5nIGluZGl2aWR1YWwgc2F1c2FnZXMgbXVzdCBiZSBhcyBzbWFsbCBhcyBwb3NzaWJsZS4gRm9yIGluc3RhbmNlLCBpZiB0aGVyZSBhcmUgdHdvIHNhdXNhZ2VzIGFuZCBzaXggdGFzdGVycyAodGhlIGZpcnN0IHRlc3QgY2FzZSBiZWxvdyksIGl0IGlzIHN1ZmZpY2llbnQgdG8gc3BsaXQgZWFjaCBzYXVzYWdlIGludG8gdGhyZWUgZXF1YWwgcGFydHMsIG1ha2luZyBhIHRvdGFsIG9mIGZvdXIgY3V0cy4gT24gdGhlIG90aGVyIGhhbmQsIGlmIHRoZXJlIGFyZSB0aHJlZSBzYXVzYWdlcyBhbmQgZm91ciB0YXN0ZXJzICh0aGUgc2Vjb25kIHRlc3QgY2FzZSBiZWxvdyksIG9uZSBwb3NzaWJpbGl0eSBpcyBjdXR0aW5nIG9mZiB0aHJlZSBxdWFydGVycyBvZiBlYWNoIHNhdXNhZ2UuIFRob3NlIGxhcmdlciBwYXJ0cyB3aWxsIGVhY2ggZ28gdG8gb25lIG9mIHRoZSB0YXNyZXJzLCB3aGlsZSB0aGUgZm91cnRoIHRhc3RlciB3aWxsIGdldCB0aGUgdGhyZWUgc21hbGxlciBwaWVjZXMgKHF1YXJ0ZXJzKSBsZWZ0IG92ZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1pcmtvIHdhbnRzIHRvIHRyeSB0aGUgZmFtb3VzIHNhdXNhZ2VzLCBzbyBoZSB2b2x1bnRlZXJlZCB0byBoZWxwIEJhanMuIEhlbHAgdGhlbSBjYWxjdWxhdGUgdGhlIG1pbmltdW0gdG90YWwgbnVtYmVyIG9mIGN1dHMgbmVlZGVkIHRvIGNhcnJ5IG91dCB0aGUgZGVzaXJlZCBkaXZpc2lvbi4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBwb3NpdGl2ZSBpbnRlZ2VycywgTiBhbmQgTSAoMSAmbGU7IE4sIE0gJmxlOyAxMDApLCB0aGUgbnVtYmVyIG9mIHNhdXNhZ2VzIGFuZCB0YXN0ZXJzLCByZXNwZWN0aXZlbHkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgbWluaW11bSBudW1iZXIgb2YgY3V0cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d