Description
有三个正整数a,b,c(0 < a,b,c < 10^12)，其中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
思路：这道题这一看之下让人很懵，虽然知道是用gcd的逆向思维，却不懂该怎么做。最大公约数其实就是a和c都是b的倍数，我们要找的就是b最小的那个符合条件的倍数。如果c不符合条件，那就让c +=b，使得c一直都是b的倍数。
#include <cstdio>
#include <iostream>
#include <cmath>
#include <
string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#define ll long long
ll n, a, b, c;
ll gcd(ll x, ll y)
{
if(x%y ==
0)
return y;
return gcd(y, x%
y);
}
int main()
{
scanf("%lld", &
n);
while(n--
)
{
scanf("%lld%lld", &a, &
b);
c = b*
2;
//让c从最小的开始计算，c最小的情况就是b的二倍
while(gcd(a, c) != b)c += b;
//保证c是b的倍数
printf(
"%lld\n", c);
}
return 0;
}
转载于:https://www.cnblogs.com/RootVount/p/10982191.html
相关资源：JAVA上百实例源码以及开源项目
