题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1722点击打开链接
Cake
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6110 Accepted Submission(s): 2964
Problem Description
一次生日Party可能有p人或者q人参加,现准备有一个大蛋糕.问最少要将蛋糕切成多少块(每块大小不一定相等),才能使p人或者q人出席的任何一种情况,都能平均将蛋糕分食.
Input
每行有两个数p和q.
Output
输出最少要将蛋糕切成多少块.
Sample Input
2 3
Sample Output
4
Hint
将蛋糕切成大小分别为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块。
解题思路：
因为本题是要求：求出最少要将蛋糕切成多少块。因此我们先分析给出的样例，两个人和三个人的情况下，如果我们什么都不管，直接切，切6份就可以，但在此处，显然6 > 4，因此就想到会有重叠利用的刀数。
如图：
常规思路：当2个人的时候，我们就按照黑色的竖线，从圆心连接两条直线到圆上，就相当于切了两刀，此时刚好将圆平分。接着我们再切四刀（如紫色线条所示），就可以将蛋糕分为6份，平均分给三个人。也就是说我们这样做出来的答案应该是6，但与题目所给不符，因此我们采取了另一种方法。
最少思维方法：
我们在一开始用黑色竖线的两刀，将蛋糕切成两半之后，因为要找最少，所以我们会思考之前的切痕是否还可以再次利用。由此我们就再利用之前的刀痕，加上两条紫色新的切痕，就可以将蛋糕切成3份，分别分给三人。此时要将蛋糕最少切成4块，满足样例，成功找到正确答案。
在我们刚刚实践的过程中，就巧妙地发现了，每次重叠的都是两次人数的Gcd.因此如下代码所示：
AC代码：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;long long gcd(long long x,long long y)
{if(y == 0) //很重要！！！！！return x;return gcd(y,x % y);
}int main()
{long long n,m;while(~scanf("%lld %lld",&n,&m)) {printf("%lld\n",n + m - gcd(n,m));}return 0;
} //很重要！！！！！return x;return gcd(y,x % y);
}int main()
{long long n,m;while(~scanf("%lld %lld",&n,&m)) {printf("%lld\n",n + m - gcd(n,m));}return 0;
}