結果

問題 No.12 限定された素数
ユーザー ynq1242ynq1242
提出日時 2014-10-28 13:00:47
言語 C++11
(gcc 11.4.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,062 bytes
コンパイル時間 685 ms
コンパイル使用メモリ 87,512 KB
実行使用メモリ 17,016 KB
最終ジャッジ日時 2024-06-09 17:46:45
合計ジャッジ時間 2,759 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
16,340 KB
testcase_01 AC 47 ms
16,756 KB
testcase_02 AC 41 ms
16,280 KB
testcase_03 AC 48 ms
16,220 KB
testcase_04 AC 42 ms
16,056 KB
testcase_05 AC 46 ms
16,096 KB
testcase_06 AC 42 ms
16,304 KB
testcase_07 AC 44 ms
16,172 KB
testcase_08 AC 44 ms
16,208 KB
testcase_09 AC 46 ms
16,360 KB
testcase_10 AC 45 ms
16,292 KB
testcase_11 AC 44 ms
16,416 KB
testcase_12 AC 41 ms
16,092 KB
testcase_13 AC 41 ms
16,700 KB
testcase_14 AC 45 ms
16,712 KB
testcase_15 AC 42 ms
16,336 KB
testcase_16 AC 44 ms
17,016 KB
testcase_17 AC 40 ms
16,196 KB
testcase_18 AC 39 ms
16,364 KB
testcase_19 AC 40 ms
16,912 KB
testcase_20 WA -
testcase_21 AC 46 ms
16,240 KB
testcase_22 AC 42 ms
16,060 KB
testcase_23 AC 40 ms
16,588 KB
testcase_24 AC 42 ms
16,200 KB
testcase_25 AC 43 ms
16,564 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