結果
問題 | No.308 素数は通れません |
ユーザー |
![]() |
提出日時 | 2019-03-30 18:43:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,407 bytes |
コンパイル時間 | 7,089 ms |
コンパイル使用メモリ | 401,128 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-15 22:25:07 |
合計ジャッジ時間 | 8,315 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 106 WA * 1 |
ソースコード
#include "bits/stdc++.h" using namespace std; #ifdef _DEBUG #include "dump.hpp" #else #define dump(...) #endif #include <boost/multiprecision/cpp_int.hpp> namespace mp = boost::multiprecision; using Int = mp::cpp_int; #define int long long #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--) #define all(c) begin(c),end(c) const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f; const int MOD = 1'000'000'007; template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; } template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; } // エラトステネスの篩 vector<char> eratos(int n) { vector<char> is_prime(n + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i*i <= n; i++) if (is_prime[i]) { int j = i + i; while (j <= n) { is_prime[j] = false; j += i; } } return is_prime; } // (a*b) % mod template<typename Int> Int modmul(Int a, Int b, Int mod) { Int x = 0, y = a % mod; while (b > 0) { if (b & 1)x = x + y % mod; y = y * 2 % mod; b >>= 1; } return x % mod; } // mod^2 が long long の最大値より大きければオーバーフローするので掛け算に modmul を使う template<typename Int> Int modpow(Int a, Int e, Int mod) { Int res = 1; while (e > 0) { if (e & 1)res = modmul(res, a, mod); a = modmul(a, a, mod); e >>= 1; } return res; } // 素数判定(Miller-Rabin primality test) // 2^24程度から // long long で2^32以上を判定する場合は modpow で modmul を使う // millerRabinPrimalityTest(n, 5) template<typename Int> bool millerRabinPrimalityTest(Int x, int iteration) { if (x < 2)return false; if (x != 2 && x % 2 == 0)return false; Int s = x - 1; while (s % 2 == 0)s /= 2; for (int i = 0; i < iteration; i++) { Int a = rand() % (x - 1) + 1, tmp = s; Int mod = modpow(a, tmp, x); while (tmp != x - 1 && mod != 1 && mod != x - 1) { mod = modmul(mod, mod, x); tmp *= 2; } if (mod != x - 1 && tmp % 2 == 0)return false; } return true; } signed main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; if (N < 50) { auto e = eratos(N); static const int di[] = { 1,0,-1,0 }; static const int dj[] = { 0,1,0,-1 }; using State = tuple<int, int, int>; rep(w, 1, N + 1) { dump(w); vector<bool> f(N + 1); int H = (N - 1) / w + 1, W = w; auto inrange = [&](int i, int j) { return i >= 0 && i < H && j >= 0 && j < W; }; auto bfs = [&](int si, int sj, int gi, int gj) { queue<State> q; q.emplace(0, si, sj); while (q.size()) { int d, ci, cj; tie(d, ci, cj) = q.front(); q.pop(); if (ci == gi && cj == gj)return d; rep(i, 0, 4) { int ni = ci + di[i], nj = cj + dj[i]; int nx = ni * w + nj + 1; if (!inrange(ni, nj))continue; if (nx > N)continue; if (e[nx])continue; if (f[nx])continue; f[nx] = true; q.emplace(d + 1, ni, nj); } } return -1LL; }; auto res = bfs(0, 0, (N - 1) / w, (N - 1) % w); dump(res); if (res != -1) { cout << w << endl; break; } } } else { for (int w = 8;; w += 2) { if (millerRabinPrimalityTest(Int(1 + w), 5))continue; if (((N - 1) % w) == 0 && millerRabinPrimalityTest(Int(N - w), 5))continue; cout << w << endl; break; } } return 0; }