Codeforces #181 Div2. E. Empire Strikes Back

さてE。Dより正答者が多いけど、自分はこちらの方が苦戦した。
http://codeforces.com/contest/300/problem/E

問題

数列A[i]が与えられる。
が整数となる最小の整数Nを答えよ。

解法

まず、各A[i]!に対し、A[i]以下の素数が何回登場するかを数え上げる。
数Nに対し、問題の分数が整数になるかどうかはN!に含まれる各素数の数の和がA[i]!毎の素数の和以上かどうかで求めることができる。
よってあとは２分探索をすればよい。

int K;
ll nnp[10000002],A[1000001];

int np;
int prime[1000000];
const int prime_max = 10000003;
static int p[prime_max];
void cprime() {
	int i,j;
	
	np=0;
	ZERO(p);
	for(i=2;i<prime_max;i++) {
		if(p[i]) continue;
		prime[np++]=i;
		for(j=i*2;j<prime_max;j+=i) p[j]=i;
	}
}

int okok(ll M) {
	ll k,t,l;
	
	FOR(k,np) {
		if(nnp[prime[k]]==0) continue;
		t=0;
		l=prime[k];
		while(l<=M) {
			t += M/l;
			l*=prime[k];
		}
		if(t<nnp[prime[k]]) return 0;
	}
	return 1;
}

void solve() {
	int f,r,i,j,k,l, x,y,ma,num,nt;
	int Q,N,K;
	
	cprime();
	
	K=GETi();
	FOR(i,K) A[i]=GETi();
	sort(A,A+K);
	
	j=0;
	for(i=0;j<K;i++) {
		while(A[j]<i && j<K) j++;
		nnp[i]=K-j;
	}
	
	for(j=i;j>=2;j--) {
		if(p[j] && nnp[j]) {
			nnp[p[j]]+=nnp[j];
			nnp[j/p[j]]+=nnp[j];
			nnp[j]=0;
		}
	}
	
	ll L=1;
	ll R=1LL<<60;
	while(R-L>0) {
		ll mid=(R+L)/2;
		
		if(okok(mid)) R=mid;
		else L=mid+1;
	}
	
	cout << L << endl;
	
	
	return;
}

まとめ

元の問題文は辺に物語仕立てなおかげでわかりにくいな。