题解 | 小红的数字分裂

#include <bits/stdc++.h>
using namespace std;
using ll= long long;
int main() {
    ll n;
    cin>>n;
    vector<int>v(n,0);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    ll a=0;
    for(int i=0;i<n;i++){
        a=gcd(a,v[i]);
    }
    ll cnt=0;
    for(int i=0;i<n;i++){
        int temp=v[i];
        if(temp!=a){
            cnt+=temp/a-1;
        }
    }
    cout<<cnt;
}
// 64 位输出请用 printf("%lld")

数字分裂，观察得知，最小步骤得到的最后相同数字也就是整个数组的最大公因数，所以遍历每个数字判断拆解成最大公因数的步骤即可