hdoj2504 最大公约数

又见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
有三个正整数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

题目实际上就是在考察最大公约数，只不过这一次是已知其中一个数和那两个数的最大公约数，求满足条件的另一个数的最小值。

个人思路：

由于两个数的最大公约数不大于那两个数中的最大值，而题目中那两个数与最大公约数不相等，因此可以让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;
}

至于求最大公约数的方法当然就是欧几里得算法（辗转相除法）喽。
记得在高中时，数学老师跟我们讲辗转相除法，那时候我就觉得：确实比小学的方法要牛。
好像以前还学过一种方法，现在有点想不起来了，那种方法主要用减法。

---

个人想法，仅供参考，如果你有什么意见，欢迎和我一起交流。