yukicoder : No.12 限定された素数

まだ割と簡単。
http://yukicoder.me/problems/34

問題

0～9のうち幾つかの数字が与えられる。

1～5,000,000までの整数の間で、ある区間K～Lを取る。
この際、K～L中の素数に含まれる各桁の整数の集合が与えられた数値群と一致するようにしたい。

区間長L-Kの最大値を求めよ。

解法

まず1～5000000までの素数P[i]を求める。
各素数P[i]から始め、P[i+1]、P[i+2]…と登場する数値を列挙していく。
この際、P[i]～P[j]が与えられた数値群と一致するなら、K=P[i-1]+1、L=P[j+1]-1が解の候補になる。
後は各P[i]に対してL-Kの最大値を求めればよい。

const int prime_max = 5000001;
int NP,prime[500000],divp[prime_max];
int mask[500000],mm;
void cprime() {
	int i,j;
	for(i=2;i<prime_max;i++) if(divp[i]==0) {
		prime[NP++]=i;
		for(j=i;j<prime_max;j+=i) divp[j]=i;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	prime[NP++]=0;
	cprime();
	prime[NP++]=5000000;
	
	FOR(i,NP) {
		j=prime[i];
		while(j) mask[i] |= 1<<(j%10), j/=10;
	}
	cin>>i;
	while(i--) cin>>x, mm |= 1<<x;
	if(mm==1023) return _P("4999999\n");

	int ret=-1;
	for(i=1;i<NP;i++) {
		int ma=0;
		FOR(j,NP-i) {
			ma |= mask[i+j];
			if(ma & (~mm)) break;
			if(ma==mm) ret=max(ret,prime[i+j+1]-1-(prime[i-1]+1));
		}
	}
	cout << ret << endl;
}

まとめ

難しくはないが、面白い設定の問題。