TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1721
  • Problem
  • P1721【语法基础】最大公约数
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

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

    Input Format

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

    Output Format

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

    Sample Input

    5
    12 8 54 69 46

    Sample Output

    4 2 3 23

    Hint

    注:求两个数的最大公约数可选择使用辗转相除法:
    ①若 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