2018-12-22 acm日常 HDU

H - Problem H HDU - 2504

有三个正整数a,b,c(0<a,b,c<10^6)，其中c不等于b。若a和c的最大公约数为b，现已知a和b，求满足条件的最小的c。
Input
第一行输入一个n，表示有n组测试数据，接下来的n行，每行输入两个正整数a,b。
Output
输出对应的c，每组测试数据占一行。
Sample Input
2
6 2
12 4
Sample Output
4
8
思路：a，c的最大公因数为b，求c，则从c=2b开始探测。
刚开始打acm的时候天真地认为只要a!=c就可以了。
后面ac了，发现需要把判断条件改一改，要严格判断。
注意：欧几里得算法别写错！！！！

ac代码：

//miku saiko
#include<iostream>
using namespace std;
// 迭代法（递推法）：欧几里得算法，计算最大公约数 
int gcd(int m, int n)
{
	while (m>0)//注意：这里是默认n>m的状态，若n<m这个式子需要改变
	{
		int c = n % m;
		n = m;
		m = c;
	}
	return n;
}
int main()
{
	long long n, a, b, c;
	cin >> n;
	for (int i = 0; i<n; i++)
	{
		long long j = 3;
		cin >> a >> b;
		c = 2 * b;
		for (;gcd(a,c)!=b; j++)//公因数不为b则继续探测。
		{
			c = j * b;
		}
		cout << c << endl;
	}
	return 0;
}

之前的错误代码：

#include<iostream>
using namespace std;
int main()
{
	long long n, a, b, c;
	cin >> n;
	for (int i=0;i<n;i++)
	{
		long long j = 3;
		cin >> a >> b;
		c = 2 * b;
		for (;a==c;j++)
		{
			c = j * b;
		}
		cout << c << endl;
	}
    return 0;
}