HDU 1722(分蛋糕 规律性题目)

spoiler posted @ 2011年4月17日 01:19 in 未分类 , 1947 阅读

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

题目分析:p+q-gcd(p+q)

代码:

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

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter