結果

問題 No.12 限定された素数
ユーザー ynq1242ynq1242
提出日時 2014-10-28 13:00:47
言語 C++11
(gcc 13.3.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,062 bytes
コンパイル時間 1,101 ms
コンパイル使用メモリ 85,488 KB
実行使用メモリ 14,820 KB
最終ジャッジ日時 2024-12-30 13:52:17
合計ジャッジ時間 3,719 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<sstream>
#include<algorithm>
#include<map>
#include<complex>
#include<ctime>
#include<set>
using namespace std;


#define li			long long int
#define rep(i,to)	for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)	for(li i=(li)(start);i<((li)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(li)n,sizeof(v))
#define bit(n)		(1ll<<(li)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define EPS 1e-10
#define ETOL 1e-8
#define MOD 1000000007
#define F first
#define S second
#define p2(a,b)		cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		cout<<a<<"\t"<<b<<"\t"<<c<<endl

bool isp[5005000];
bool digits[505050][10];
bool use[10];
bool alive[505050];
vector<li> primes;

int main(){
	rep(i,5005000)isp[i]=true;
	isp[0]=isp[1]=false;
	repp(i,2,sqrt(5005000)+3){
		if(isp[i])
		for(li j=2; i*j<5005000; j++){
			isp[i*j]=false;
		}
	}
	rep(i,5005000)if(isp[i])primes.pb(i);
	//cout<<sz(primes)<<endl;
	li n;
	cin>>n;
	rep(i,10)use[i]=false;
	rin{
		li x;
		cin>>x;
		use[x]=true;
	}

	li res=-1;

	rep(i,sz(primes)){
		alive[i]=true;
		li now=primes[i];
		rep(j,10)digits[i][j]=false;
		while(now>0){
			digits[i][now%10]=true;
			if(digits[i][now%10] && !use[now%10])alive[i]=false;
			now/=10;
		}
	}

	li left=1, right=0;
	rep(i,sz(primes)){
		bool use_now[10]={false};
		while(i<sz(primes) && alive[i]){
			rep(j,10)if(digits[i][j])use_now[j]=true;
			i++;
		}
		if(i<sz(primes))right=primes[i]-1;
		else right=5000000;

		bool ok=true;
		rep(j,10)if(use[j]&&!use_now[j])ok=false;
		if(ok){
			//p2(left, right);
			res=max(res, right-left);
		}
		left=right+2;
	}

	cout<<res<<endl;



	return 0;
}
0