HDU-2504

在此之前需要了解一下欧几里得算法，这是一个用于求最大公约数的算法。
事实上就是辗转相除法，你们可以翻一下你们的高中课本，或者直接百度查，都能够找到相关资料的。
那么这里假设你们能写欧几里得算法（不能的参考代码里的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;
}

这个代码的时间会比上面的代码少差不多一半时间：