未神明阿 2022-05-05 09:31 采纳率: 25%
浏览 228
已结题

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

img

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

  • 写回答

1条回答 默认 最新

  • a5156520 2022-05-05 10:13
    关注

    一个实现,如下:

    #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;
        
    } 
    
    

    img

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 5月14日
  • 已采纳回答 5月6日
  • 创建了问题 5月5日

悬赏问题

  • ¥15 MATLAB动图问题
  • ¥15 有段代码不知道怎么理解,const isToken = (config.headers || {}).isToken === false
  • ¥100 采用栈和深度优先算法对我的代码进行修改显示路径
  • ¥15 pointnet2包安装
  • ¥20 射频功率问题,解答者有酬谢!
  • ¥80 构建降雨和积水的预测模型
  • ¥15 #Qt Transform setTransform()在鼠标拖动移动视角是一致在原地不动,无法变换视角(细微观察似乎视图有在原地抖动),无法变换视角(细微观察似乎视图有在原地抖动)
  • ¥50 如何利用无人机拍摄的数码照片测量鸟卵的长短径
  • ¥100 github贡献者给与奖励
  • ¥15 使用DS18B20+ESP8266获取温度数据返回-127.00