Cake
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2208 Accepted Submission(s): 1134
Problem Description
一次生日Party可能有p人或者q人参加,现准备有一个大蛋糕.问最少要将蛋糕切成多少块(每块大小不一定相等),才能使p人或者q人出席的任何一种情况,都能平均将蛋糕分食. Input
每行有两个数p和q.
Output
输出最少要将蛋糕切成多少块.
Sample Input
2 3
Sample Output
4Hint将蛋糕切成大小分别为1/3,1/3,1/6,1/6的四块即满足要求. 当2个人来时，每人可以吃1/3+1/6=1/2 , 1/2块。 当3个人来时，每人可以吃1/6+1/6=1/3 , 1/3, 1/3块。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1722０
感觉每次遇到最大公约数的题目都理解无能，这道题无非又是最大公约数的应用。
将蛋糕切成几块，我想可以把它理解为切多少刀更加易懂。开始思考的是依照蛋糕的大小来计算，结果涉及到了浮点型数据处理，求余，求商等让人很乱，结果当然也不能ＡＣ，所以果断弃了。
一个数ａ的因数ｂ，放在这道题中可以使人理解成，想要把蛋糕分成ａ块，先切ｂ刀，（一次切的长度为蛋糕的半径）再在剩余的ｂ份中，平均分成ａ／ｂ份，每份需要再切ａ／ｂ－１刀，其余蛋糕切ａ－ｂ刀，共切ａ刀。
而如果另一个数ｃ与ａ有公因数ｂ，则设第一次切好后蛋糕摆放没有变，则需要先切ｂ刀，在平均每份切ｃ／ｂ－１刀，共再切ｃ－ｂ刀，而为了达到块数最小，尽量使用第一次切好的刀缝。第一次的ｂ刀已经不用切取。故最终需要切ａ＋ｃ－ｄ次，分成ａ＋ｃ－ｄ块。
由此可见，为了得到最小块数，需要ｄ最大，是两个数的最大公约数。
ＡＣ的代码粘过来就是
#include <stdio.h>
int gcd(int a,int b)
{
if(a%b==0)
return b;
else
return gcd(b,a%b);
}
void main()
{
int a,b,d;
double c;
while(scanf("%d%d",&a,&b)!=EOF)
{
if(a>b)
{
a=a+b;
b=a-b;
a=a-b;
}
printf("%d\n",a+b-gcd(a,b));
}
}
