HDU 2504(又见GCD)

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

题目:

有三个正整数a,b,c(0<a,b,c<10^6),其中c不等于b。若a和c的最大公约数为b,现已知a和b,求满足条件的最小的c。

刚刚开始的时候写错了,没考虑太多,直接a/b如果不等于1 就a/b-1然后乘以b!

其实枚举就行了:

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

总结:唉,汗颜!下次细心!UP!


登录 *


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