結果

問題 No.12 限定された素数
ユーザー ynq1242ynq1242
提出日時 2014-10-28 13:00:47
言語 C++11
(gcc 11.4.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,062 bytes
コンパイル時間 597 ms
コンパイル使用メモリ 80,276 KB
実行使用メモリ 17,376 KB
最終ジャッジ日時 2023-08-28 23:13:02
合計ジャッジ時間 3,452 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 55 ms
16,060 KB
testcase_01 AC 60 ms
17,144 KB
testcase_02 AC 56 ms
16,400 KB
testcase_03 AC 64 ms
16,108 KB
testcase_04 AC 58 ms
16,192 KB
testcase_05 AC 60 ms
16,888 KB
testcase_06 AC 57 ms
17,344 KB
testcase_07 AC 58 ms
16,288 KB
testcase_08 AC 60 ms
16,228 KB
testcase_09 AC 61 ms
16,464 KB
testcase_10 AC 59 ms
16,100 KB
testcase_11 AC 61 ms
16,476 KB
testcase_12 AC 58 ms
16,300 KB
testcase_13 AC 57 ms
16,088 KB
testcase_14 AC 60 ms
16,524 KB
testcase_15 AC 58 ms
16,324 KB
testcase_16 AC 62 ms
17,196 KB
testcase_17 AC 55 ms
16,060 KB
testcase_18 AC 55 ms
16,472 KB
testcase_19 AC 55 ms
15,996 KB
testcase_20 WA -
testcase_21 AC 61 ms
16,108 KB
testcase_22 AC 57 ms
16,356 KB
testcase_23 AC 58 ms
16,256 KB
testcase_24 AC 58 ms
16,492 KB
testcase_25 AC 60 ms
17,376 KB
権限があれば一括ダウンロードができます

ソースコード

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