又見(jiàn)GCD
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 15358 Accepted Submission(s): 6448
Problem Description
有三個(gè)正整數(shù)a,b,c(0<a,b,c<10^6)，其中c不等于b。若a和c的最大公約數(shù)為b，現(xiàn)已知a和b，求滿足條件的最小的c。

Input
第一行輸入一個(gè)n，表示有n組測(cè)試數(shù)據(jù)，接下來(lái)的n行，每行輸入兩個(gè)正整數(shù)a,b。

Output
輸出對(duì)應(yīng)的c，每組測(cè)試數(shù)據(jù)占一行。

Sample Input
2
6 2
12 4

Sample Output
4
8

題目實(shí)際上就是在考察最大公約數(shù)，只不過(guò)這一次是已知其中一個(gè)數(shù)和那兩個(gè)數(shù)的最大公約數(shù)，求滿足條件的另一個(gè)數(shù)的最小值。

個(gè)人思路：

由于兩個(gè)數(shù)的最大公約數(shù)不大于那兩個(gè)數(shù)中的最大值，而題目中那兩個(gè)數(shù)與最大公約數(shù)不相等，因此可以讓c最小取b+1，后判斷gcd(a,c)是否等于b.

參考代碼：

#include <cstdio>
using namespace std;
int gcd(int a,int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b,a%b);
}
int gcd_ch(int a,int b) {
    int c;
    for (c = b+1;;c++) {
        if (gcd(a,c) == b) {
            break;
        }
    }
    return c;
}
int main() {
    int a,b;
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &a, &b);
        int c = gcd_ch(a,b);
        printf("%d\n", c);
    }
    return 0;
}

至于求最大公約數(shù)的方法當(dāng)然就是歐幾里得算法（輾轉(zhuǎn)相除法）嘍。
記得在高中時(shí)，數(shù)學(xué)老師跟我們講輾轉(zhuǎn)相除法，那時(shí)候我就覺(jué)得：確實(shí)比小學(xué)的方法要牛。
好像以前還學(xué)過(guò)一種方法，現(xiàn)在有點(diǎn)想不起來(lái)了，那種方法主要用減法。

個(gè)人想法，僅供參考，如果你有什么意見(jiàn)，歡迎和我一起交流。