Cake

Cake (抽象出欧几里得)

Cake Problem Description一次生日Party可能有p人或者q人参加,现准备有一个大蛋糕.问最少要将蛋糕切成多少块(每块大小不一定相等),才能使p人或者q人出席的任何一种情况,都能平均将蛋糕分食. 
Input

每行有两个数p和q. 
Output
输出最少要将蛋糕切成多少块. 
Sample Input2 3 
Sample Output4 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块。 
AuthorLL 

题目意思很清楚，不用多说，公式是 p+q-gcd(p,q)

举个例子：4 6，用一个矩形来切割，如下图

蓝色点线表示4等分线 红色实线表示6等分线，让蛋糕（矩形）可以平分为4份需要（4刀）和6份需要（6刀），总共需要10刀，但因为其中有两条线是重合的，没有必要切两次，所以应该减掉这两刀，就只剩下

10-2=8刀了。对于任何p和q，他们重合的线的数量就是他们的GCD，所以就~~~~~

 

实现1，普通的循环，Exe.Time=15ms Code.len=338B
#include <stdio.h>
#include <stdlib.h>
int maxy(int m,int n)
{
    int r;
    if(m<n)
    {
        r=m;
        m=n;
        n=r;
    }
    do
    {
       r=m%n;
       m=n;
       n=r;
       }while(n!=0);
       return (m);
}
int main()
{
    int p,q;
    while(scanf("%d %d",&p,&q)!=EOF)
    {
        printf("%d\n",p+q-maxy(p,q));
    }
     return 0;
}

 

实现2，递归函数,Exe.Time=218ms,Code.len=259B
#include <iostream>
#include <math.h>
using namespace std;

int gcd(int a, int b) {
    /*如果a>b,b可能是最大公约数，去除a中能被b整出余下的部分a1如果a1!=0,说明b不是gcd，继续
     则b>a1 ,a1可能是最大公约数，继续直到an=0说明此时的b=0,a中保存了gcd*/
      /*如果a<b,则第一次gcd(b, a%b)边实现了他们的交换*/

    return b ? gcd(b, a%b) : a;
}

int main() {
    int p, q;
    while(cin>>p>>q) {
        cout << p + q - gcd(p, q) << endl;
    }

    return 0;
}