【GCD（最大公约数）】HDU1722-Cake

本文主要是介绍【GCD（最大公约数）】HDU1722-Cake，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目】

Cake

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 3489 Accepted Submission(s): 1815

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 9为例，我们来数实现每种情况的目的需要切的刀数。首先是6个人，由于蛋糕是圆的，根据这道题的特殊情况，我们下刀时需要从蛋糕圆心处下刀并向外切，即，沿着蛋糕的半径去切，不能沿直径。因此要把蛋糕分别分成6份和9份的刀数分别是6和9。
	所以现在问题转化为，要切到最少的块数，该怎么切。由上面的分析，可以知道，要想块数最少，我们下刀的刀数要最少，也就是说，我们两次下刀时，尽量使下刀的痕迹重合越多越好，来看下面的图：

	这张图中，被红线分割的是1/6的情况，被灰线分割的是1/9的情况，兰色则表示红线与灰线重合的线。图中所画的情况表示重合线最多的情况。可以看到有3条线重合。
	可是为什么会是3条？
	原因是，分割6条时，每条线占到1/6 , 9条时为1/9，所以灰线中间每隔两条线都会与红线重合一次，换句话来讲，就是因为3是6和9的最大公约数。
	到这里，相信大家应该明白最少的刀数该怎么算了吧，两种情况的刀数相加，再减去想要刀数最少时重合的刀数数目，即 答案=（p+q-（p和q的最大公约数）） 。下面来看一下我的代码实现吧~

【代码】
#include__int64 GCD(__int64 a,__int64 b);
int main()
{
__int64 p,q;
while(scanf("%I64d%I64d",&p,&q)!=EOF)
printf("%I64d\n",q+p-GCD(p,q));
}
__int64 GCD(__int64 a,__int64 b)
{
if(a%b==0)
return b;
else
return GCD(b,a%b);
}
另外代码中的__int64相当于数字很大的int变量，用%I64d接收。