読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

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

yukicoder

まだ割と簡単。
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;
}

まとめ

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

広告を非表示にする