Codeforces

Luogu

分析

显然可以将 $k_i$ 相同的点放在一起处理,则点数变为 $5000$ 级别。

考虑如何从 $1$ 走到 $n!$。将 $n!$ 质因数分解并把所有质因数从大到小排序,然后依次乘过去即可。

既然要计算树的重心,考虑从 $1$ 开始走,每次向 $size$ 最大的子树移动,直到 $maxsize\leq \frac{n}{2}$。

现在的问题是如何计算每个点在哪颗子树中,显然在它的最大质因子对应的子树中。

实现上需要求出 $n!$ 的每个质因子的次数,做一个前缀和即可;然后对每个数维护一个指针表示最大质因子即可。

具体实现有一些细节,详见代码。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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 N=5000+10,K=5000;

int n,cnt[N],f[N][N],p[N],o[N];

int main() {
    n=read();
    for (int i=1;i<=n;++i) ++cnt[read()];
    for (int i=2;i<=K;++i) {
        memcpy(f[i],f[i-1],sizeof(f[i]));
        for (int j=2,t=i;j<=t;++j)
            while (t%j==0) ++f[i][j],t/=j;
    }
    ll now=0;
    for (int i=0;i<=K;++i) {
        if (!cnt[i]) p[i]=0;
        else {
            for (int j=1;j<=i;++j)
                if (f[i][j]) p[i]=j,now+=1ll*f[i][j]*cnt[i];
        }
    }
    ll ans=now;
    while ("longge ak ioi") {
        memset(o,0,sizeof(o));
        for (int i=0;i<=K;++i) o[p[i]]+=cnt[i];
        int v=max_element(o+1,o+K+1)-o,sz=o[v];
        if ((sz<<1)<=n||v==1) break;
        now-=sz,now+=n-sz; ans=min(ans,now);
        for (int i=0;i<=K;++i) {
            if (p[i]==1) continue;
            if (p[i]!=v) { p[i]=1; continue; }
            --f[i][p[i]];
            while (p[i]>1&&!f[i][p[i]]) --p[i];
        }
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2020 年 04 月 14 日 07 : 25 PM