CF300E. Empire Strikes Back

题目链接（是的我越来越懒了。。）

题目大意及数据范围：

数据范围很大。“最小”二字让我们考虑二分，但是上界...不会爆long long让你写高精吧？

我们可以发现，∑a一定满足条件，所以上界是1e13。为什么满足呢？因为C(n+m,n)是整数，所以n!| ( (n+m)!/m! ) ，所以满足。

然后问题只剩下怎么满足判断整除了。数很大，肯定要分解。n！的分解容易解决，因为我们只需考虑1e7范围内的质数即可，每次计算效率约为1e7/ln，总的复杂度能接受。所以只需解决各a!如何分解。显然不能像n那个挨个质数地试，冗余过多，我们得考虑把各ai和在一起。既然都是阶乘，我们只需考虑每个数x对几个a产生贡献即可(满足x≤a的a有几个)，挨个将x分解的复杂度我们还是可以接受的（毕竟CF的机子，还开5s）。

总时间复杂度O(alog(max{a}) )

#include <bits/stdc++.h>

using namespace std;

#define rep(i,l,r) for(int i=l;i<=r;++i)

#define per(i,r,l) for(int i=r;i>=l;--i)

typedef long long ll;

const int N=1e6+,V=1e7;

int n,a[N];

ll ans[V+];//ans[j]

namespace Euler{

    bool h[V+];

    int pr[N],len,miz[V+];//miz[x]=no

    void sieve(){

        rep(i,,V){

            if(!h[i]){

                pr[++len]=i;

                miz[i]=len;

            }

            int val;

            for(int j=;j<=len&&(val=pr[j]*i)<=V;++j){

                h[val]=;

                miz[val]=j;

                if(i%pr[j]==) break;

            }

        }

    }

    void dvd(int x,int ct){//divide x to ans  ans[no]

        if(x==) return ;

        int no=miz[x],P=pr[no];

        while(x%P==){

            ans[no]+=ct;

            x/=P;

        }

        dvd(x,ct);

    }

    void calc(){

        int L=;

        rep(i,,V){

            while(a[L]<i&&L<=n) ++L;

            //ct=n-L+1

            dvd(i,n-L+);

        }

    }

    bool ck(ll val){

        rep(j,,len){

            ll sum=pr[j],P=pr[j],ad=;

            while(sum<=val){

                ad+=(val/sum);

                sum*=P;

            }

            if(ad<ans[j]) return ;

        }

        return ;

    }

}

using Euler::sieve;

using Euler::calc;

using Euler::ck;

int main(){

    sieve();

    scanf("%d",&n);

    rep(i,,n) scanf("%d",&a[i]);

    sort(a+,a++n);

    calc();

    ll L=,R=1e13;

    while(L<R){

        ll mid=(L+R)>>;

        if(ck(mid)) R=mid;

        else L=mid+;

    }

    printf("%lld\n",L);

    return ;

}