HDU 2054 又見GCD(水題??)

又見GCD

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 15221    Accepted Submission(s): 6397

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
        

Source 《ACM程式設計》短學期考試_軟體工程及其他專業

原題連結:http://acm.hdu.edu.cn/showproblem.php?pid=2504 分析: 知道a,c的最大公約數為b,已知a,b，求最 小的c也就是已知gcd（a,c) = b，求最小的c。不要天真的的以為c=2b; 不容忽視的是，題目要求b! = c,也就是c值從2b開始，然後一步步加c再判斷a,c的最大公約數是否等于b，滿足時輸出c.

AC代碼:

#include <iostream>
using namespace std;
int GCD(int x,int y)
{
    return y==0?x:GCD(y,x%y);
}
int main()
{
    int t,a,b;
    cin>>t;
    while(t--)
    {
        cin>>a>>b;
        int c = 2*b;
        while(GCD(a,c)!=b)
        {
            c+=b;
        }
        cout<<c<<endl;
    }
    return 0;
}