TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1721
  • 题目
  • P1721【语法基础】最大公约数
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    输入n个整数,求出相邻两个整数的最大公约数,输出结果。

    输入格式

    共两行,第一行一个整数n(n<=10000)表示有n个整数
    第二行有n个整数(<=10000),以空格作为间隔。

    输出格式

    只有一行,共n-1个空格间隔的整数,表示依次求出的相邻两数的最大公约数,以

    样例输入

    5
    12 8 54 69 46

    样例输出

    4 2 3 23

    提示

    注:求两个数的最大公约数可选择使用辗转相除法:
    ①若 r 是 a ÷ b 的余数, 则
       a和b的最大公约数 = b和r的最大公约数
    ②若r=0则b就是a跟b的最大公约数

    比如: 求2784 和 2322 的最大公约数

    2784 ÷ 2322 余数为462 根据上面第①条
    2784和2322的最大公约数=2322和462的最大公约数
    2322÷462 余数为12 根据上面第①条
    2322和462的最大公约数=462和12的最大公约数
    462÷12 余数为6 根据上面第①条
    462和12 的最大公约数=12 和 6 的最大公约数
    12÷6 余数为0
            根据上面第②条 就求出12和6 的最大公约数为6
            也就求出了2784和2322的最大公约数为6