【杭电oj】1722 - Cake（数论，GCD）

Cake

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2914 Accepted Submission(s): 1527 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块。

Author

LL

Source

HZIEE 2007 Programming Contest

据说是数论，然而我现在的知识层面还不懂什么是数论 = =！

这道题公式很简单，就是a+b-gcd(a,b)

为什么呢？

我就试着解释一下：

如果有a个人要来，那么要切a刀，b个人来，就切b刀。

但是，他们切的有可能两刀切到了同一个地方，这样的切的次数为 gcd(a,b) 想想也是可以理解的，所以公式就出来了。

代码如下：

#include <stdio.h>
int GCD(int a,int b)
{
	if (a%b==0)
		return b;
	int t;
	t=a%b;
	GCD(b,t);
}
int main()
{
	int a,b;
	int g;
	int ans;
	while (~scanf ("%d%d",&a,&b))
	{
		g=GCD(a,b);
		ans=a+b-g;
		printf ("%d\n",ans);
	}
	return 0;
}