BZOJ

分析

这个状态设的好神仙啊qwq

设$f[i]$表示所有数除以$i$再向下取整后的答案,显然最终答案为$f[1]$。

转移时直接枚举素数转移过去就行了,详见代码。

分析

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100000+10;

int v[MAXN],low[MAXN],p[MAXN],cnt=0;

inline void sieve(int n) {
    for (re int i=2;i<=n;++i) {
        if (!v[i]) p[++cnt]=i,low[i]=i;
        for (re int j=1;j<=cnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1,low[i*p[j]]=p[j];
            if (i%p[j]==0) break;
        }
    }
}

int a[MAXN],f[MAXN];

int main() {
    int n=read(),mx=0;
    for (re int i=1;i<=n;++i) a[i]=read(),mx=max(mx,a[i]);
    sieve(mx);
    for (re int i=mx;i>=1;--i) {
        for (re int j=1;j<=n;++j) f[i]+=a[j]/i;
        for (re int j=1;j<=cnt&&i*p[j]<=mx;++j) {
            int tmp=f[i*p[j]];
            for (re int k=1;k<=n;++k) tmp+=a[k]/i%p[j];
            f[i]=min(f[i],tmp);
        }
    }
    printf("%d\n",f[1]);
    return 0;
}
最后修改:2019 年 09 月 24 日 08 : 52 PM