变换

D：变换

先把所有数去除掉他们的最大公约数，这个数不影响答案。

然后剩下所有的数求出他们的素数因子，素数因子的个数就是答案。

如5 6 7就是选5让其他数都乘以5，选6其他数都乘以2，再乘以3，选7再让其他数都乘以7.可以保证这个是最优解。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
    ll s=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<1)+(s<<3)+(c^48);c=getchar();
    }
    return f*s;
}
const int N=1555555;
int a[N],num,prime[N];
bool vis[N];
int main(){
    int n=read();
    for(int i=2;i<=1e6;i++){//欧拉筛
        if(!vis[i])prime[++num]=i;
        for(int j=1;prime[j]*i<=1e6&&j<=num;j++){
            vis[prime[j]*i]=true;
            if(i%prime[j]==0)break;
        }        
    }
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    int s=a[1],ans=0;
    for(int i=2;i<=n;i++){
        s=__gcd(s,a[i]);
    }
    for(int i=1;i<=n;i++)a[i]/=s;
    for(int i=1;i<=n;i++){
        for(int j=1;prime[j]*prime[j]<=a[i];j++){
            while(a[i]%prime[j]==0)a[i]/=prime[j],ans++;//筛选素数因子个数
        }
        if(a[i]!=1)ans++;
    }
    cout<<ans<<endl;
}