10330. Cutting SausagesConstraints
Time Limit: 1 secs, Memory Limit: 256 MB
Description
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.
Sample Input样例1：2 6样例2：3 4样例3：6 2Sample Output样例1：4样例2：3样例3：0Problem Source
COCI 2013.9/2014年每周一赛第一场
非常值得令人思考的一道题，参考了大神的资料才得以做出：
分析：
看上面的图已经显而易见了，可以把人看成一段段线，香肠也是如此，然后，最少刀数的办法就是尽量使人与人之间的端点和香肠之间的断点（不是用刀切的）重合；
那么，在人的那条线上的没有重合的点数就是最少的刀数。
怎么求不重合的点数呢？首先m个人有m + 1个端点，但是两端的端点是不用考虑的，也就是只用考虑m – 1个端点。
设每个人的长度为y，，每条香肠的长度为x，那么首先有x * n = m * y；
设i个人后与j条香肠后会有一个端点重合，即i * y = j * x；
那么在人里面的个数就是（x * n
分子分母都是相同的，说明在人里面和在香肠里面的个数是相同的；
消去上式中的x和y，得：m / i = n / j；
设它们等于k；
那么k显然是m和n的公共的约数；
而为了使人和香肠之间的断点尽可能的多，我们就要使i和j尽可能的短，那么由m / k = i以及n / k = j知道，k就要尽可能的大；
所以k就是m，n的最大公约数；
x * n
那么切的最少刀数，也就是不重合的考虑的点数m – 1 减去考虑的重合的点数 (gcd(n, m) – 1)；
代码：
#include <stdio.h>int gcd(int a, int b) {if (b == 0)return a;elsereturn gcd(b, a % b);}int main() {int n, m;scanf("%d%d", &n, &m);printf("%d\n", m – 1 – (gcd(n, m) – 1));return 0;}
可以以心感悟，以此沉淀，足矣;耳听佳音，目极美好，
