题目链接

https://ac.nowcoder.com/acm/contest/7606/D

解题思路

刚拿到以为是树状数组的题，心想完了，一个数据也过不去了。
结果仔细一看，原来不是树状数组的题目，舒服多了，还是一个数据没过。

不知道大家有没有做过一道蓝桥的题（可能是），题目找不到了，大致意思是n堆馒头，每堆数量不一样，每天能将n-1个馒头分到n-1个堆里，问最少几天每堆变得一样。
就这意思，正着想的话，选出最多的一堆不分，其他每堆一个，模拟下去；
反向操作一下，每天都让最多的一堆减一个，直到所有堆的馒头数都相等，这和选n-1个加一个的效果一样吧。

对应到本题来说，除素数和乘素数都一样，算出的最终答案也是一样的。
相较乘而言，我们肯定选择除，乘的数据有可能爆吧。
首先，我们可以忽略掉所有数的最大公约数，它对结果没影响（不用多解释吧），而且这个最小公倍数，就是我们希望最后操作完所有数后，每个数变成的数；
其次，根据上面馒头例题，我们反向操作一下，每次对一个数除素数，直到除到1，因为最后每个数变成最小公倍数，所以每个数先除完了最小公倍数，剩下的商变成1就行了。所有数除素数除到1的次数和？这不就是分解质因数嘛。
对每个数分解质因数就行了，用到 欧拉筛 ，不会的同学（包括我）可以补一下。

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+100;
const int NN=1e6;
int n,num,gcd,a[N],vis[N],prime[N],ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        if(i!=1) gcd=__gcd(gcd,a[i]);
        else gcd=a[i];        
    }
    for(int i=1;i<=n;i++) {
        a[i]/=gcd;
    }
    for(int i=2;i<=NN;i++){
        if(!vis[i]) prime[++num]=i;
        for(int j=1;j<=num;j++){
            if(i*prime[j]>NN) break;
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break; 
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;prime[j]*prime[j]<=a[i];j++)
            while(a[i]%prime[j]==0) ans++,a[i]/=prime[j];
        if(a[i]!=1) ans++;
    }
    cout<<ans<<endl;
}