切蛋糕

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3439 Accepted Submission(s): 1642

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块。

如图,切1刀得到1块,切2刀得到2块.在同一起始点切p刀和q刀,得到的总块数减去重合的切线,就是所得总的块数.
重合切线即是p和q的最大公约数r.
?:最大公约数的本质是什么呢?为什么重合切线就是最大公约数?因为假设p和q都各是一个圆,那么将这两个圆各分成r分,切线肯定是一样的.再比如p和q都各是一条长度为1的钢管,重量分别为p和q,将它们分成r份,那么切点是一样的,只是每段的质量不同而已. r就像篮子,p和q都可以均匀放到r个篮子里一样.

cake cut

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
#include<cmath>
#include<cstdlib>
#define MAX (1 << 20)
using namespace std;


unsigned gcd(unsigned x, unsigned y)
{
    return y?gcd(y, x%y):x;
}


int main()
{
    unsigned x, y;
    while(scanf("%d %d", &x, &y)!=EOF)
    {
        printf("%d\n", x+y - gcd(x, y));
    }
    return 0;
}

参考链接