HDOJ2504 ( 又见GCD ) 【辗转相除法（欧几里德法）最小公倍数】

 1 #include <cstdio>
 2 using namespace std;
 3 int gcd(int a,int c)
 4 {
 5     int t;
 6     if(c<a)    {t=a;a=c;c=t;}
 7     while (t=c%a,t!=0)
 8     {
 9         c=a;
10         a=t;
11     }
12     return a;
13 }
14 int main()
15 {
16     int a,b,c,cas;
17     scanf("%d",&cas);
18     while (cas--)
19     {
20         scanf("%d %d",&a,&b);//c一定是b的倍数
21         c=b<<1;
22         while(b!=gcd(a,c))
23             c+=b;
24         printf("%d\n",c);
25     }
26     return 0;
27 }