結果
問題 | No.308 素数は通れません |
ユーザー |
👑 |
提出日時 | 2019-01-18 16:02:38 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 257 ms / 1,000 ms |
コード長 | 3,899 bytes |
コンパイル時間 | 1,717 ms |
コンパイル使用メモリ | 164,172 KB |
実行使用メモリ | 7,916 KB |
最終ジャッジ日時 | 2024-06-13 02:58:03 |
合計ジャッジ時間 | 8,588 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 107 |
ソースコード
import std.conv, std.stdio, std.string;import std.algorithm, std.array, std.bigint, std.container, std.math, std.range, std.regex, std.typecons;import core.bitop;class EOFException : Throwable { this() { super("EOF"); } }string[] tokens;string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }int readInt() { return readToken().to!int; }long readLong() { return readToken().to!long; }real readReal() { return readToken().to!real; }void chmin(T)(ref T t, in T f) { if (t > f) t = f; }void chmax(T)(ref T t, in T f) { if (t < f) t = f; }int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp)>> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); }int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); }immutable LIM = 10^^6;bool[] isnp;void prepare() {isnp = new bool[LIM];isnp[0] = isnp[1] = true;foreach (i; 2 .. LIM) {if (!isnp[i]) {for (int j = 2 * i; j < LIM; j += i) {isnp[j] = true;}}}}bool[][] doIt(int H, int W, int N) {auto A = new bool[][](H, W);foreach (x; 0 .. H) foreach (y; 0 .. W) {A[x][y] = (1 + x * W + y <= N) && isnp[1 + x * W + y];}auto vis = new bool[][](H, W);void dfs(int x, int y) {vis[x][y] = true;foreach (dir; 0 .. 4) {const xx = x + [+1, 0, -1, 0][dir];const yy = y + [0, +1, 0, -1][dir];if (0 <= xx && xx < H && 0 <= yy && yy < W && A[xx][yy]) {if (!vis[xx][yy]) {dfs(xx, yy);}}}}dfs(0, 0);return vis;}int solveSmall(int N) {foreach (W; 1 .. N) {const H = (N + W + 1) / W;const vis = doIt(H, W, N);if (vis[(N - 1) / W][(N - 1) % W]) {return W;}}return -1;}bool isPrime(BigInt n) {if (n <= 1 || n % 2 == 0) return (n == 2);BigInt power(BigInt a, BigInt e, BigInt m) {BigInt x = a, y = 1;for (; e != 0; e >>= 1, x = x * x % m) if (e & 1) y = y * x % m;return y;}BigInt d;int r, s;for (d = n - 1, s = 0; d % 2 == 0; d >>= 1, ++s) {}foreach (a; 2 .. 100) if (a < n) {BigInt ad = power(BigInt(a), d, n);if (ad == 1) continue;for (r = 0; r < s; ++r) {if (ad == n - 1) break;ad = ad * ad % n;}if (r == s) return false;}return true;}void main() {prepare();/*foreach (W; 1 .. 30) {const vis = doIt(2 * W, W, 2 * W * W);foreach (x; 0 .. 2 * W) {foreach (y; 0 .. W) {writef("%s%4s%s", vis[x][y] ? "[" : " ", 1 + x * W + y, vis[x][y] ? "]" : " ");}writeln();}writeln();}return;*/try {for (; ; ) {const N = readToken().to!BigInt;int ans;if (N <= 20 * 20) {ans = solveSmall(cast(int)(N));} else {foreach (W; [8, 14, 17, 19, 20]) {auto vis = new bool[W^^2];bool ok;void dfs(BigInt n) {if (n <= N && !isPrime(n)) {if (N - n >= W^^2) {ok = true;return;}if (!vis[cast(int)(N - n)]) {vis[cast(int)(N - n)] = true;const y = cast(int)((n - 1) % W);dfs(n - W);dfs(n + W);if (0 <= y - 1) {dfs(n - 1);}if (y + 1 < W) {dfs(n + 1);}}}}dfs(N);if (ok) {ans = W;break;}}}writeln(ans);}} catch (EOFException e) {}}