题解 | 小红的数字分裂

//朱波做了半天做完了才发现这题其实是找最大公约数，下面是朱波的方法（不建议学习所以不解释了）
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long

signed main() {
    int n;
    cin >> n;
    vector<int>a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    int sum = accumulate(a.begin(), a.end(), 0LL);
    vector<int>mod;
    for (int i = 1; i < n; i++) mod.push_back((a[i] - a[0]) % a[0]);
    sort(mod.begin(), mod.end());
    int mod_min = 0;
    for (int i = 0; i < mod.size(); i++) {
        if (mod[i]) {
            mod_min = mod[i];
            break;
        }
    }
    if (mod_min == 0) cout << sum / a[0] - n;
    else {
        int mid;
        if (a[0] % mod_min == 0) cout << sum / mod_min - n;
        else {
            mid = a[0] % mod_min;
            while (mod_min) {
                int temp = mid;
                mid = mod_min % mid;
                if (mid == 0) {
                    cout << sum / temp - n;
                    break;
                } else mod_min = temp;
            }
        }
    }

    return 0;
}

//下面再附上更优的解法请各位享用
signed main() {
    int n;
    cin >> n;
    vector<int> a(n);
    
    int g = 0, sum = 0;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        g = gcd(g, a[i]);
        sum += a[i];
    }
    
    // 最终值 t 就是最大公约数 g
    int ans = sum / g - n;
    cout << ans << endl;
    
    return 0;
}
// 64 位输出请用 printf("%lld")