結果
問題 | No.12 限定された素数 |
ユーザー |
![]() |
提出日時 | 2017-01-10 18:02:49 |
言語 | D (dmd 2.109.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,049 bytes |
コンパイル時間 | 1,686 ms |
コンパイル使用メモリ | 148,736 KB |
実行使用メモリ | 51,968 KB |
最終ジャッジ日時 | 2024-06-12 06:17:05 |
合計ジャッジ時間 | 6,336 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 WA * 2 |
ソースコード
import std.algorithm;import std.array;import std.ascii;import std.container;import std.conv;import std.math;import std.numeric;import std.range;import std.stdio;import std.string;import std.typecons;void log(A...)(A arg) { stderr.writeln(arg); }int size(T)(in T s) { return cast(int)s.length; }const X = 5000000;void main() {auto isPrime = new bool[X + 1];auto nextPrime = new int[X + 1];auto prevPrime = new int[X + 1];{isPrime[] = true;isPrime[0] = isPrime[1] = false;int prev = 2; for (int j = 4; j <= X; j += 2) isPrime[j] = false;for (int i = 3; i <= X; i++) {if (isPrime[i]) {nextPrime[prev] = i;prevPrime[i] = prev;prev = i;for (int j = i + i; j <= X; j += i) {isPrime[j] = false;}}}nextPrime[4999999] = X + 1;prevPrime[2] = 0 - 1;}int N; readf("%d\n", &N);auto A = readln.chomp.split(" ").map!(to!int).array;int set = 0; {foreach (a; A) {set |= 1 << a;}}int cur = 0;int ans = -1;int from = -1;for (int i = 2; i <= X; i++) {if (isPrime[i]) {auto s = to!string(i);int prev = cur;foreach (c; s) {int t = cast(int)(c - '0');cur |= 1 << t;}if ( (cur & set) == cur ) {if (from < 0) {from = i;if ( (cur & set) == set ) {ans = max(ans, nextPrime[i] - prevPrime[i] - 2);}}} else {if (from >= 0 && prev == set) {ans = max(ans, i - prevPrime[from] - 2);}from = -1;cur = 0;}}}if (from >= 0 && cur == set) {ans = max(ans, X - prevPrime[from] - 2);}writeln(ans);}