Cake

HDU - 1722 Cake

题目描述：

一次生日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块。

题目分析：
首先我们把这个蛋糕看成是一个单位圆：

很明显，其中有条黄色线和蓝色线重合了，这样圆就被分割成了4个部分，因为2和3的最大公约数是1，所以在割蛋糕的时候会有一刀相重合，这样相当于蛋糕被切了四刀，即被分成了4块。
所以核心公式为：n = a + b - GCD(a,b),GCD是求最大公约数,即重合的。

http://blog.csdn.net/tigerisland45/article/details/51151529 该链接中有求最大公约数的三种方法，方便读者学习

以下是AC代码:

#include<iostream>
using namespace std;
int gcd(int a , int b)      //递归法：欧几里得算法，计算最大公约数
{
    return a==0?b:gcd(b%a,a);
}
int main()
{
    int x,y;
    while(cin>>x>>y)
    {
        int n = x + y - gcd(x,y);
        cout<<n<<endl;
    }
}