hoj 2504 又見GCD

題目連結

我在做這道題時，沒有想到用枚舉；我的思路是分情況讨論

1.如果a=b，（因為題目中隻說了b不等于c，是以我考慮到了a=b的情況），取c=2*a即可；

2.如果a和b不相等，并且a/b=2，那麼可取c=3*b；

3.如果a和b不相等，并且a/b與2的最大公因數為1（如果不為1，則肯定c不為最大公因數），取c=2*b；

4.如果a和b不相等，并且a/b與2的最大公因數不為1（如果不為1，則肯定c不為最大公因數），則利用循環找出與a/b的最大公因數為1的數值，再利用乘以b即可；

代碼如下：

#include<stdio.h>
int gcd(int a, int b) {
	if (b == 0) return a;
	else return gcd(b, a%b);
}
int main()
{
	int n;
	scanf("%d", &n);
	while (n--)
	{
		int a, b;
		int i = 2;
		scanf("%d%d", &a, &b);
		if (a / b > 2 && gcd(a / b, i) == 1) printf("%d\n", b*2);
		if (a / b == 2) printf("%d\n", b * 3);
		if (a == b) printf("%d", a * 2);
		if (a / b > 2 && gcd(a / b, i) != 1)
		{
			i++;
			while (gcd(a / b, i) != 1)
			{
				i++;
			}
			printf("%d\n", b*i);
		}
	}
    return 0;
}