问题 [016]：N个整数的最大公约数 (难度：中等) 竞技编程-提高思维

题目描述 给定N个正整数A1, A2, ..., AN，求它们的最大公约数。

输入格式 输入包含一个整数N，表示正整数的个数。接下来是N个整数，表示需要求最大公约数的数列。

• 2 ≤ N ≤ 10^5
• 2 ≤ Ai ≤ 10^18
• 所有输入均为整数

输出格式 输出N个整数的最大公约数。

示例

输入示例 1：

3
12 18 24

输出示例 1：

6

解释：12、18和24的最大公约数是6，因此输出6。

时间复杂度分析 本题可以通过迭代计算多个数的最大公约数，利用欧几里得算法来求得两数的最大公约数，时间复杂度为O(log(Ai))。对于N个数，我们需要执行N-1次两两计算，因此总时间复杂度为O(N * log(Ai))，在N最大为10^5，Ai最大为10^18时，算法能够在规定时间内完成。