結果
問題 | No.12 限定された素数 |
ユーザー | tottoripaper |
提出日時 | 2014-11-16 05:43:10 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 37 ms / 5,000 ms |
コード長 | 1,347 bytes |
コンパイル時間 | 447 ms |
コンパイル使用メモリ | 61,044 KB |
実行使用メモリ | 11,368 KB |
最終ジャッジ日時 | 2023-08-15 22:27:24 |
合計ジャッジ時間 | 2,493 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 36 ms
11,116 KB |
testcase_01 | AC | 37 ms
11,108 KB |
testcase_02 | AC | 36 ms
11,108 KB |
testcase_03 | AC | 37 ms
11,108 KB |
testcase_04 | AC | 36 ms
11,356 KB |
testcase_05 | AC | 37 ms
11,360 KB |
testcase_06 | AC | 37 ms
11,352 KB |
testcase_07 | AC | 37 ms
11,220 KB |
testcase_08 | AC | 37 ms
11,232 KB |
testcase_09 | AC | 36 ms
11,296 KB |
testcase_10 | AC | 36 ms
11,232 KB |
testcase_11 | AC | 37 ms
11,236 KB |
testcase_12 | AC | 36 ms
11,220 KB |
testcase_13 | AC | 36 ms
11,280 KB |
testcase_14 | AC | 36 ms
11,368 KB |
testcase_15 | AC | 36 ms
11,368 KB |
testcase_16 | AC | 37 ms
11,236 KB |
testcase_17 | AC | 36 ms
11,232 KB |
testcase_18 | AC | 36 ms
11,216 KB |
testcase_19 | AC | 37 ms
11,352 KB |
testcase_20 | AC | 36 ms
11,352 KB |
testcase_21 | AC | 36 ms
11,356 KB |
testcase_22 | AC | 36 ms
11,292 KB |
testcase_23 | AC | 37 ms
11,108 KB |
testcase_24 | AC | 37 ms
11,296 KB |
testcase_25 | AC | 37 ms
11,308 KB |
ソースコード
#include <cstdio> #include <iostream> #include <vector> #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,j) FOR(i,0,j) typedef long long ll; std::vector<int> primes; bool isPrime[5000101]; int xs[348518]; int N, A[10]; int main(){ std::fill(isPrime, isPrime+5000101, true); std::fill(&xs[0], &xs[0]+348518, 0); primes.push_back(0); primes.push_back(2); xs[1] = 0x4; for(int i=4;i<=5000100;i+=2){isPrime[i] = false;} int length = 2; for(ll i=3;i<=5000100;i+=2){ if(isPrime[i]){ primes.push_back(i); int x = i; while(x > 0){xs[length] |= 1 << (x % 10); x /= 10;} length += 1; for(ll j=i*i;j<=5000100ll;j+=i){ isPrime[j] = false; } } } scanf("%d", &N); int restricted = 0; REP(i, N){int a; scanf("%d", &a); restricted |= 1 << a;} int res = -1; for(int i=1,j=1;i<348514;){ int y = 0; while(j < 348514 && (~restricted & xs[j]) == 0){ y |= xs[j]; j += 1; } if(y == restricted){ res = std::max(res, std::min(primes[j],5000001)-primes[i-1]-2); } i = j+1; j = i; } printf("%d\n", res); }