首页 > ACM题库 > HDU-杭电 > hdu 2504 又见GCD-组合数学-[解题报告]C++
2014
02-09

hdu 2504 又见GCD-组合数学-[解题报告]C++

又见GCD

问题描述 :

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

输入:

第一行输入一个n,表示有n组测试数据,接下来的n行,每行输入两个正整数a,b。

输出:

第一行输入一个n,表示有n组测试数据,接下来的n行,每行输入两个正整数a,b。

样例输入:

2
6 2
12 4

样例输出:

4
8

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

解题思路:

由于a和c的最大公约数是b,所以a = xb,b=yb。现在相当于已知x,求y。

我们由上面可知x和y一定是互质的。只要枚举一下最小的与x互质的自然数就是y了,但是题目要求不等于b,所以要加上不相等的条件。。

代码如下:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;

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

int main()
{
	int ncase;
	int a, b, c;
	scanf("%d", &ncase);
	while(ncase--)
	{
		scanf("%d%d", &a, &b);
		int temp = a / b;
		for(int i = 2; ; ++i)
		{
			if(i * b != b && Gcd(temp, i) == 1)
			{
				printf("%d\n", i * b);
				break;
			}
		}
	}
	return 0;
}

解题转自:http://blog.csdn.net/niushuai666/article/details/7011619


  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!