KUSAC - Kusac

no tags 

 

Mirko has given up on the difficult coach job and switched to food tasting instead. Having skipped 
breakfast like a professional connoisseur, he is visiting a Croatian cured meat festival. The most 
renowned cook at the festival, Marijan Bajs, has prepared N equal sausages which need to be 
distributed to M tasters such that each taster gets a precisely equal amount. He will use his trusted knife 
to cut them into pieces. 
In order to elegantly divide the sausages, the number of cuts splitting individual sausages must be as 
small as possible. For instance, if there are two sausages and six tasters (the first test case below), it is 
sufficient to split each sausage into three equal parts, making a total of four cuts. On the other hand, if 
there are three sausages and four tasters (the second test case below), one possibility is cutting off three 
quarters of each sausage. Those larger parts will each go to one of the tasrers, while the fourth taster 
will get the three smaller pieces (quarters) left over. 
Mirko wants to try the famous sausages, so he volunteered to help Bajs. Help them calculate the 
minimum total number of cuts needed to carry out the desired division. 

Mirko has given up on the difficult coach job and switched to food tasting instead. Having skipped 

breakfast like a professional connoisseur, he is visiting a Croatian cured meat festival. The most 

renowned cook at the festival, Marijan Bajs, has prepared N equal sausages which need to be 

distributed to M tasters such that each taster gets a precisely equal amount. He will use his trusted knife 

to cut them into pieces. 

In order to elegantly divide the sausages, the number of cuts splitting individual sausages must be as 

small as possible. For instance, if there are two sausages and six tasters (the first test case below), it is 

sufficient to split each sausage into three equal parts, making a total of four cuts. On the other hand, if 

there are three sausages and four tasters (the second test case below), one possibility is cutting off three 

quarters of each sausage. Those larger parts will each go to one of the tasrers, while the fourth taster 

will get the three smaller pieces (quarters) left over. 

Mirko wants to try the famous sausages, so he volunteered to help Bajs. Help them calculate the 

minimum total number of cuts needed to carry out the desired division. 

 

Input

The first and only line of input contains two positive integers, N and M (1 ≤ N, M ≤ 100), the number 

of sausages and tasters, respectively.

Output

The first and only line of output must contain the required minimum number of cuts.

Example

Input:
2 6 

Output:
4

Input:
3 4 

Output:
3

Input:
6 2 

Output:
0

hide comments
kaleoum: 2020-01-29 09:53:05

e n=55&m=79
ans 78

smso: 2019-04-07 06:53:31

play with some test cases and use a recursive function

Wumbolo: 2016-07-08 06:31:31

there is a very simple closed formula :) Input Constraints are waaay too low

chhavipatel: 2016-01-25 21:15:45

can anyone provide some tricky test cases (n and m >50)

Last edit: 2016-01-25 22:05:49
cute_girl_1: 2016-01-12 16:51:18


Last edit: 2016-01-12 16:52:19
Anuj Agrawal: 2015-05-14 19:47:06

Can anybody provide the ans for test case n=55&m=79.

Petar Bosnjak: 2014-06-26 14:07:55

This problem is ok now , everyone who got WA or TLE can send their solutions again
--Francky--> (2) You have to make a rejudge, and explain why the last rejudge was cancelled. Thanks.

Last edit: 2014-06-26 16:09:22
Francky: 2014-06-18 08:28:47

It seems rejudged had been cancelled. Can you explain what happened ?

Tomislav Babic: 2014-06-17 13:17:04

@Francky
127 people got AC with wrong files because error was in only one test case which is not even official. Input in that test case was 0 and output 0. All other test cases were correct.
--Francky--> Many thanks.

Last edit: 2014-06-17 15:26:16
Tomislav Babic: 2014-06-17 13:13:59

Test cases problem solved! All solution are rejudged.


Added by:Tomislav Babic
Date:2013-10-05
Time limit:0.109s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:COCI 2013 1. round