欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU ACM Steps:Cake

程序员文章站 2024-01-15 17:43:22
...

HDU ACM Steps:Cake

题目描述

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

输入

每行有两个数p和q.

输出

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

输入样例

2 3

输出样例

4
提示
将蛋糕切成大小分别为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块

思路

这道题有一定思维难度,首先我们要认为蛋糕是圆形的,这样切了多少刀就会有多少份蛋糕。
先把一个蛋糕均匀切成2份,再拿另外一个蛋糕切成3份,再把两个蛋糕重合在一起,可以发现切的线有些可以重合。而重合部分就是我们可以少切的刀数,也就是gcd(2,3)(可以通过相遇周期理解)。
因此可以得到这道题的公式a+b-gcd(a,b)。

代码

#include<stdio.h>

int a,b; 

int gcd(int x,int y)
{
	return y ? gcd(y,x%y) : x;
}

int main()
{
	while(~scanf("%d %d",&a,&b))
	{
		printf("%d\n",a+b-gcd(a,b));
	}
	return 0;
 } 

相关标签: ACM Steps