欧几里得算法又称辗转相除法，是求最大公约数的绝佳方法。
又见GCD
Time Limit : 1000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 18 Accepted Submission(s) : 9
Font: Times New Roman |Verdana |Georgia
Font Size: ← →
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！
代码如下：
<span style="font-size:12px;">#include<stdio.h>
#include<stdlib.h>
int gcd(int a,int b,int c)
{
int i;
while(c>0)
{
i=a%c;//当i=0时，这里的c就是最大公约数
a=c;
c=i;
}
if(a==b)//辗转相除法求最大公约数
return 1;
else return 0;
}
int main()
{
int t,i,a,b,c;
scanf("%d",&t);
while(t--)
{
i=0;//必须在此给i赋值，否则第二组数时直接输出c=b+1；
scanf("%d%d",&a,&b);
for(c=b+1;c<=a;c++)
{
if(c%b==0)
i=gcd(a,b,c);//返回值只有1和0
if(i==1)
{
printf("%d\n",c);
break;
}
}
}
//system("pause");
return 0;
}</span>