首页 > ACM题库 > HDU-杭电 > HDU 1722 Cake-组合数学-[解题报告] C++
2013
12-21

HDU 1722 Cake-组合数学-[解题报告] C++

Cake

问题描述 :

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

输入:

每行有两个数p和q.

输出:

输出最少要将蛋糕切成多少块.

样例输入:

2 3

样例输出:

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

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1722

解题思路:

这个想了半天也没想出什么好的办法。。。。。。google之~~

举个例子:4 6,用一个矩形来切割,其实应该是圆的。这里边界也得加上,因为首位其实是相连的。。。自己动手画下圆形的蛋糕模拟。

b3aadd00446a58fb267fb5a3

蓝色点线表示4等分线 红色实线表示6等分线,让蛋糕(矩形)可以平分为4份需要(4刀)和6份需要(6刀),总共需要10刀,但因为其中有两条线是重合的,没有必要切两次,所以应该减掉这两刀,就只剩下10-2=8刀了。对于任何p和q,他们重合的线的数量就是他们的公约数。

所以公式就是:p+q-gcd(p,q)

 

代码如下:

#include<stdio.h>

int Gcd(int m, int n)
{
	return m == 0 ? n : Gcd(n % m, m);
}

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

 

解题报告转自:http://blog.csdn.net/niushuai666/article/details/7011139


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。