算法题：yhy的Robot

问题描述

2035年，智能机器人在各行各业中的应用已经十分普遍了，毕竟它做事时的精度与力量比一个普通人是强多了。

yhy的运输队里就有一个，是用来装卸货物的。

这天，他们的任务是要把n根废旧的条形钢材运送到钢铁厂重新冶炼。这些钢材长短不同（有些还特别的长），为了便于运输，只好把它们切割成小段。所以，他给机器人的任务是：把这些钢材切割并装上卡车。

等机器人做完这事的时候，yhy一看结果，自己都被逗笑了：机器人的逻辑就是和人不同啊——装在车上的所有小段的钢材，居然长度都是一样的（以米为单位），而且，还是所有可行方案中，切割次数最少的那种方案！

如果告诉你最开始那n 根钢材的长度，你能算出机器人切割出的小段的长度吗？

输入格式

第一行为整数n,(1<=n<=1e5),表示原始钢材的数量。

第二行中是n个用空格分开的整数，表示每根废旧钢材的长度（以米为单位），已知这些整数不小于1，不超过400000。

输出格式

只有一个整数，表示机器人切割出来的每个小段的长度。

样例1

输入

4
4
22
8
12

输出

2

样例2

输入

5
18 52 63 95 47

输出

1

解决方案

思路

最大公约数

代码

#include <iostream>

using namespace std;

int gcd(int a, int b) {
    if (b == 0)
        return a;
    if (b > a) {
        swap(a, b);
    }

    return gcd(b, a % b);
}

int main() {

    int n;
    cin >> n;

    int arr[100005];
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    int t = arr[0];
    for (int i = 1; i < n; ++i) {
        t = gcd(t, arr[i]);
    }
    cout << t;
    return 0;
}