当前位置: 代码迷 >> 综合 >> hdu---Cake
  详细解决方案

hdu---Cake

热度:12   发布时间:2024-01-12 15:59:32.0

Cake

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3835 Accepted Submission(s): 1838
 
Problem Description
一次生日Party可能有p人或者q人参加,现准备有一个大蛋糕.问最少要将蛋糕切成多少块(每块大小不一定相等),才能使p人或者q人出席的任何一种情况,都能平均将蛋糕分食.
Input
每行有两个数p和q.
Output

输出最少要将蛋糕切成多少块.
Sample Input
2 3
Sample Output
4<div style="" border-bottom:="" #b7cbff="" 1px="" dashed;="" border-left:="" padding-bottom:="" 6px;="" padding-left:="" padding-right:="" font-family:="" times"="">
       
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块。
Author
LL
Source
HZIEE 2007 Programming Contest
Recommend
lcy
解题思路:看似简单一题,反正我是没有思路,不太好理解,如果想平均分为p份或q份,可以先分为b份(b为q和p的公因子,一会我们再证明此时b应该为gcd(p,q))也就是先切b刀(相当于半径的一刀);

我们可以把这b份每份平均分为p/b份(也就是把整体分为p份),每份要切(p/b)-1刀,b份共p-b刀,加上开始b刀,共p刀;

我们也可以把这b份每份平均分为q/b份(也就是把整体分为q份),每份要切(q/b)-1刀,b份共q-b刀,但开始b刀已经切好,所以共q-b刀;

共p+q-b刀为了使此值更小,需要b==gcd(q,p);也就是在切为q块或p块过程中(平均的切),尽可能使切的相同位置最多(最多为gcd())

大概目前就理解成这样

参考:http://www.xuebuyuan.com/1481582.html

http://www.jianshu.com/p/ad2921727e2a

http://blog.csdn.net/sky_fighting/article/details/8639638

代码:

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int gcd(int x,int y)
{return y==0?x:gcd(y,x%y);
}
int main()
{int a,b;while(scanf("%d%d",&a,&b)!=EOF){printf("%d\n",a+b-gcd(a,b));}return 0;
}