题解 | 小红的gcd

观察样例大胆猜测：答案是

因为任意两个数的gcd一定有一个因子是总体的gcd，也就是这个数一定是总体的倍数，连续gcd后，最终的数必然都会变成全体的最大公约数，不可能比这个还小，因为gcd最小就能让一个数减少到全体的公约数，不会使得一个数比这个全体的公约数还要小，因此我们简单证明了这个答案是最小的，另外再证明这个答案一定取得到，只需要第一个与第二个操作，第二个与第三个操作，以此类推，第一个与第二个操作变成__gcd(a1,a2)，第二个与第三个操作变成__gcd( ___gcd(a1,a2),a3)，一趟下来与求gcd(a1,a2,a3,...,an)是等价的。

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    int x;
    int k;
    cin>>n;
    cin>>k;
    for(int i=2;i<=n;i++){
        cin>>x;
        k=__gcd(k,x);
    }
    cout<<1LL*k*n;
    
}
// 64 位输出请用 printf("%lld")