在此之前需要了解一下欧几里得算法，这是一个用于求最大公约数的算法。
事实上就是辗转相除法，你们可以翻一下你们的高中课本，或者直接百度查，都能够找到相关资料的。
那么这里假设你们能写欧几里得算法（不能的参考代码里的gcd函数就行了）。
在此之前，假设x和y的最大公约数表示为gcd(x,y)
首先要注意的是c不能等于b。
有两种方法。
第一种比较简单，枚举c的值，从b+1开始从小到大一个一个枚举，直到满足条件位置。
为什么是从b+1开始呢？首先c不能等于b，其次，当c小于b的时候，由于gcd(a,c)必定是小于等于c的，所以其最大公约数不可能是b（因为gcd(a,c)<=c<b，所以gcd(a,c)<b）。所以c必定大于b。
那么知道这个的话代码就十分好写了：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b)
{
if(b==0)return a;
return gcd(b,a%b);
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
LL a,b;
scanf("%lld%lld",&a,&b);
LL c=b+1;
while(gcd(a,c)!=b)c++;
printf("%lld\n",c);
}
return 0;
}
用的时间是31ms：
image.png
第二种解法就相当于是扩展吧。要懂这个解法需要对最大公约数和素数（也叫质数）有一个比较充分的理解。
首先，由于
gcd(a,c)=b，所以我们可以假设x和y使得：
a=b*x-
c=b*y
那么显然就会有gcd(x,y)=1（这一步不懂的话可以先停下来想想为什么）
在这里，x很容易求出来（其实就是a/b），问题在于如何求最小的y使得gcd(x,y)=1
换个问法就是，求最小的y使得x和y互质。
于是我们可以对x分解质因数，那么y就只需要是一个x分解的质因数中没有出现过的质数就行了
那么事实上y就只可能是{2,3,5,7,11,13,17,19}这8个数中的一个（这8个数就是最小的8个质数）。
为什么呢？
注意到题目的数据范围，输入的数字均小于1000000。也就是说x也只可能小于1000000。
也就是说，x分解质因数后不可能同时拥有{2,3,5,7,11,13,17,19}中所有数。
因为同时拥有这些质数的最小数字是2*3*5*7*11*13*17*19=9699690>1000000，这显然超出了x可能的范围了。
那也就是说，我们肯定可以从这其中找到至少一个数，使得其不出现在x的质因数中，也就是跟x互质。
于是显然地，直接从小到大枚举这些数字就行了：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int Prime[8]={2,3,5,7,11,13,17,19};
int Solve(int a,int b)
{
int p=a/b;
for(int i=0;i<8;i++)
{
if(p%Prime[i]!=0)return Prime[i]*b;
}
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int a,b;
scanf("%d%d",&a,&b);
int c=Solve(a,b);
printf("%d\n",c);
}
return 0;
}
这个代码的时间会比上面的代码少差不多一半时间：
