输入两个正整数x,y(1<=x,y<=231-1)，求x与y的最大公因数。第一行输入一个整数n，表示测试用例的个数，以后每行输入两个正整数。每行输出一个测试样例的结果

Question

输入两个正整数x,y(1<=x,y<=231-1)，求x与y的最大公因数。第一行输入一个整数n，表示测试用例的个数，以后每行输入两个正整数。每行输出一个测试样例的结果

Answer 1

一个实现，如下：

#include <stdio.h>



int main(void){
    
    int num;
    int x,y;
    int a,b;
    int result; 
    
    scanf("%d",&num);
    
    int i=0;
    while(i<num){ //输出num组x和y的最大公因数 
        scanf("%d%d",&x,&y);
        a=x;
        b=y;
    /**
     * 辗转相减法
     * 算法参考：
     *     https://blog.csdn.net/yxdayd/article/details/44774015
    
*/
        while(1){
            if(a>b)
                a-=b;
            else if(a<b)
                b -=a;
            else{
                result=a;
                break;
            }
                
        }
        printf("GCD(%d,%d)=%d\n",x,y,result);
        i++;
    }
    
    

    
    return 0;
    
}