正经题解｜新年游戏

题面大意

你有$n$个正整数，每次可以选择一对数，$p_i$与$p_j$($i \neq j,p_i > p_j$)，然后使$p_i$ = $p_i$ - $p_j$
最终会得到一个新的序列

题意分析

要求最终序列的和最小

解题思路

每次我们用一个大的数$p_i$减去一个小的数$p_j$，操作后，$p_j$会变成那个较大的数，$p_i$会变成那个较小的数字，继续重复这个操作。我们发现与辗转相减的操作是一样的，那么实际上就是求最大公约数。

时间复杂度解析

代码演示

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,r = 0,x;
    cin >> n;
    for(int i=0;i<n;i++) {
        cin >> x;
        if (!r) r = x;
        r = __gcd(r, x);
    }
    cout << r * n<< endl;
    return 0;
}