結果
問題 | No.308 素数は通れません |
ユーザー | minami |
提出日時 | 2019-04-03 16:38:02 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 86 ms / 1,000 ms |
コード長 | 11,211 bytes |
コンパイル時間 | 3,141 ms |
コンパイル使用メモリ | 207,000 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-01 10:09:30 |
合計ジャッジ時間 | 6,305 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,944 KB |
testcase_13 | AC | 2 ms
6,944 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | AC | 2 ms
6,940 KB |
testcase_16 | AC | 2 ms
6,944 KB |
testcase_17 | AC | 2 ms
6,940 KB |
testcase_18 | AC | 2 ms
6,940 KB |
testcase_19 | AC | 2 ms
6,940 KB |
testcase_20 | AC | 2 ms
6,944 KB |
testcase_21 | AC | 2 ms
6,944 KB |
testcase_22 | AC | 2 ms
6,944 KB |
testcase_23 | AC | 2 ms
6,940 KB |
testcase_24 | AC | 2 ms
6,944 KB |
testcase_25 | AC | 2 ms
6,940 KB |
testcase_26 | AC | 2 ms
6,944 KB |
testcase_27 | AC | 2 ms
6,940 KB |
testcase_28 | AC | 2 ms
6,940 KB |
testcase_29 | AC | 2 ms
6,944 KB |
testcase_30 | AC | 2 ms
6,940 KB |
testcase_31 | AC | 2 ms
6,940 KB |
testcase_32 | AC | 2 ms
6,940 KB |
testcase_33 | AC | 2 ms
6,940 KB |
testcase_34 | AC | 2 ms
6,944 KB |
testcase_35 | AC | 2 ms
6,940 KB |
testcase_36 | AC | 2 ms
6,944 KB |
testcase_37 | AC | 2 ms
6,944 KB |
testcase_38 | AC | 2 ms
6,940 KB |
testcase_39 | AC | 2 ms
6,940 KB |
testcase_40 | AC | 2 ms
6,940 KB |
testcase_41 | AC | 2 ms
6,940 KB |
testcase_42 | AC | 2 ms
6,940 KB |
testcase_43 | AC | 2 ms
6,944 KB |
testcase_44 | AC | 2 ms
6,944 KB |
testcase_45 | AC | 3 ms
6,944 KB |
testcase_46 | AC | 2 ms
6,940 KB |
testcase_47 | AC | 2 ms
6,940 KB |
testcase_48 | AC | 2 ms
6,940 KB |
testcase_49 | AC | 2 ms
6,940 KB |
testcase_50 | AC | 2 ms
6,940 KB |
testcase_51 | AC | 2 ms
6,944 KB |
testcase_52 | AC | 2 ms
6,940 KB |
testcase_53 | AC | 3 ms
6,944 KB |
testcase_54 | AC | 2 ms
6,940 KB |
testcase_55 | AC | 2 ms
6,944 KB |
testcase_56 | AC | 3 ms
6,944 KB |
testcase_57 | AC | 2 ms
6,940 KB |
testcase_58 | AC | 2 ms
6,944 KB |
testcase_59 | AC | 3 ms
6,940 KB |
testcase_60 | AC | 2 ms
6,944 KB |
testcase_61 | AC | 2 ms
6,944 KB |
testcase_62 | AC | 3 ms
6,944 KB |
testcase_63 | AC | 8 ms
6,940 KB |
testcase_64 | AC | 2 ms
6,940 KB |
testcase_65 | AC | 2 ms
6,940 KB |
testcase_66 | AC | 2 ms
6,944 KB |
testcase_67 | AC | 2 ms
6,940 KB |
testcase_68 | AC | 2 ms
6,940 KB |
testcase_69 | AC | 2 ms
6,940 KB |
testcase_70 | AC | 2 ms
6,944 KB |
testcase_71 | AC | 2 ms
6,940 KB |
testcase_72 | AC | 2 ms
6,940 KB |
testcase_73 | AC | 2 ms
6,940 KB |
testcase_74 | AC | 2 ms
6,944 KB |
testcase_75 | AC | 2 ms
6,944 KB |
testcase_76 | AC | 4 ms
6,940 KB |
testcase_77 | AC | 2 ms
6,940 KB |
testcase_78 | AC | 2 ms
6,944 KB |
testcase_79 | AC | 2 ms
6,940 KB |
testcase_80 | AC | 8 ms
6,940 KB |
testcase_81 | AC | 14 ms
6,944 KB |
testcase_82 | AC | 2 ms
6,940 KB |
testcase_83 | AC | 2 ms
6,940 KB |
testcase_84 | AC | 22 ms
6,940 KB |
testcase_85 | AC | 2 ms
6,944 KB |
testcase_86 | AC | 28 ms
6,944 KB |
testcase_87 | AC | 34 ms
6,940 KB |
testcase_88 | AC | 2 ms
6,944 KB |
testcase_89 | AC | 2 ms
6,940 KB |
testcase_90 | AC | 63 ms
6,940 KB |
testcase_91 | AC | 2 ms
6,944 KB |
testcase_92 | AC | 2 ms
6,944 KB |
testcase_93 | AC | 2 ms
6,944 KB |
testcase_94 | AC | 2 ms
6,944 KB |
testcase_95 | AC | 2 ms
6,940 KB |
testcase_96 | AC | 6 ms
6,940 KB |
testcase_97 | AC | 2 ms
6,940 KB |
testcase_98 | AC | 2 ms
6,944 KB |
testcase_99 | AC | 14 ms
6,940 KB |
testcase_100 | AC | 17 ms
6,944 KB |
testcase_101 | AC | 86 ms
6,944 KB |
testcase_102 | AC | 3 ms
6,944 KB |
testcase_103 | AC | 2 ms
6,944 KB |
testcase_104 | AC | 3 ms
6,940 KB |
testcase_105 | AC | 2 ms
6,940 KB |
testcase_106 | AC | 22 ms
6,940 KB |
ソースコード
#include "bits/stdc++.h" using namespace std; #ifdef _DEBUG #include "dump.hpp" #else #define dump(...) #endif #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 Interval> bool chmax(Interval &a, const Interval &b) { if (a < b) { a = b; return true; } return false; } template<class Interval> bool chmin(Interval &a, const Interval &b) { if (b < a) { a = b; return true; } return false; } struct BigInt { static const int kBase = 1000000000; static const int kBaseDigits = 9; vector<int> d; int sign; BigInt() :sign(1) {} BigInt(long long v) { sign = 1; if (v < 0) sign = -1, v = -v; for (; v > 0; v = v / kBase) d.emplace_back(v % kBase); } BigInt(const string &s) { read(s); } bool operator<(const BigInt &v)const { if (sign != v.sign) return sign < v.sign; if (d.size() != v.d.size()) return d.size() * sign < v.d.size() * v.sign; for (int i = d.size() - 1; i >= 0; i--) if (d[i] != v.d[i]) return d[i] * sign < v.d[i] * sign; return false; } bool operator>(const BigInt &v)const { return v < *this; } bool operator<=(const BigInt &v)const { return !(v < *this); } bool operator>=(const BigInt &v)const { return !(*this < v); } bool operator==(const BigInt &v)const { return !(*this < v) && !(v < *this); } bool operator!=(const BigInt &v)const { return !(*this == v); } BigInt &operator+=(const BigInt &v) { if (sign == v.sign) { BigInt res = v; for (int i = 0, carry = 0; i < (int)max(d.size(), v.d.size()) || carry; ++i) { if (i == (int)res.d.size()) res.d.emplace_back(0); res.d[i] += carry + (i < (int)d.size() ? d[i] : 0); carry = res.d[i] >= kBase; if (carry) res.d[i] -= kBase; } return *this = res; } else return *this -= (-v); } BigInt &operator-=(const BigInt &v) { if (sign == v.sign) { BigInt tmp = abs(); if (abs() >= v.abs()) { BigInt res = *this; for (int i = 0, carry = 0; i < (int)v.d.size() || carry; ++i) { res.d[i] -= carry + (i < (int)v.d.size() ? v.d[i] : 0); carry = res.d[i] < 0; if (carry) res.d[i] += kBase; } res.trim(); return *this = res; } else return *this = -(v - *this); } else return *this += -v; } BigInt &operator*=(const BigInt &v) { return *this = *this * v; } BigInt &operator/=(const BigInt &v) { return *this = *this / v; } BigInt operator-()const { BigInt res = *this; res.sign = -sign; return res; } BigInt operator+(const BigInt &v)const { return BigInt(*this) += v; } BigInt operator-(const BigInt &v)const { return BigInt(*this) -= v; } BigInt operator*(int v)const { BigInt res = *this; res *= v; return res; } BigInt operator*(const BigInt &v)const { vector<int> a6 = convertBase(this->d, kBaseDigits, 6); vector<int> b6 = convertBase(v.d, kBaseDigits, 6); vll a(a6.begin(), a6.end()); vll b(b6.begin(), b6.end()); while (a.size() < b.size()) a.emplace_back(0); while (b.size() < a.size()) b.emplace_back(0); while (a.size() & (a.size() - 1)) a.emplace_back(0), b.emplace_back(0); vll c = karatsubaMultiply(a, b); BigInt res; res.sign = sign * v.sign; for (int i = 0, carry = 0; i < (int)c.size(); i++) { long long cur = c[i] + carry; res.d.emplace_back((int)(cur % 1000000)); carry = (int)(cur / 1000000); } res.d = convertBase(res.d, 6, kBaseDigits); res.trim(); return res; } BigInt operator/(const BigInt &v)const { return divmod(*this, v).first; } BigInt operator/(int v)const { BigInt res = *this; res /= v; return res; } BigInt operator%(const BigInt &v)const { return divmod(*this, v).second; } int operator%(int v)const { if (v < 0) v = -v; int m = 0; for (int i = d.size() - 1; i >= 0; --i) m = (d[i] + m * (long long)kBase) % v; return m * sign; } BigInt &operator*=(int v) { if (v < 0) sign = -sign, v = -v; for (int i = 0, carry = 0; i < (int)d.size() || carry; ++i) { if (i == (int)d.size()) d.emplace_back(0); long long cur = d[i] * (long long)v + carry; carry = (int)(cur / kBase); d[i] = (int)(cur % kBase); } trim(); return *this; } BigInt &operator/=(int v) { if (v < 0) sign = -sign, v = -v; for (int i = (int)d.size() - 1, rem = 0; i >= 0; --i) { long long cur = d[i] + rem * (long long)kBase; d[i] = (int)(cur / v); rem = (int)(cur % v); } trim(); return *this; } void read(const string &s) { sign = 1; d.clear(); int pos = 0; while (pos < (int)s.size() && (s[pos] == '-' || s[pos] == '+')) { if (s[pos] == '-') sign = -sign; ++pos; } for (int i = s.size() - 1; i >= pos; i -= kBaseDigits) { int x = 0; for (int j = max(pos, i - kBaseDigits + 1); j <= i; j++) x = x * 10 + s[j] - '0'; d.emplace_back(x); } trim(); } friend istream& operator >> (istream &stream, BigInt &v) { string s; stream >> s; v.read(s); return stream; } friend ostream& operator << (ostream &stream, const BigInt &v) { if (v.sign == -1) stream << '-'; stream << (v.d.empty() ? 0 : v.d.back()); for (int i = (int)v.d.size() - 2; i >= 0; --i) stream << setw(kBaseDigits) << setfill('0') << v.d[i]; return stream; } long long toLongLong()const { long long res = 0; for (int i = d.size() - 1; i >= 0; i--) res = res * kBase + d[i]; return res * sign; } string toString()const { ostringstream os; os << *this; return os.str(); } static pair<BigInt, BigInt> divmod(const BigInt &a1, const BigInt &b1) { int norm = kBase / (b1.d.back() + 1); BigInt a = a1.abs() * norm; BigInt b = b1.abs() * norm; BigInt q, r; q.d.resize(a.d.size()); for (int i = a.d.size() - 1; i >= 0; i--) { r *= kBase; r += a.d[i]; int s1 = r.d.size() <= b.d.size() ? 0 : r.d[b.d.size()]; int s2 = r.d.size() <= b.d.size() - 1 ? 0 : r.d[b.d.size() - 1]; int d = ((long long)kBase * s1 + s2) / b.d.back(); r -= b * d; while (r < 0) r += b, --d; q.d[i] = d; } q.sign = a1.sign * b1.sign; r.sign = a1.sign; q.trim(); r.trim(); return make_pair(q, r / norm); } void trim() { while (!d.empty() && !d.back()) d.pop_back(); if (d.empty()) sign = 1; } bool isZero()const { return d.empty() || (d.size() == 1 && !d[0]); } BigInt abs()const { BigInt res = *this; res.sign *= res.sign; return res; } static vector<int> convertBase(const vector<int> &a, int old_digits, int new_digits) { vector<long long> p(max(old_digits, new_digits) + 1); p[0] = 1; for (int i = 1; i < (int)p.size(); i++) p[i] = p[i - 1] * 10; vector<int> res; long long cur = 0; int cur_digits = 0; for (int i = 0; i < (int)a.size(); i++) { cur += a[i] * p[cur_digits]; cur_digits += old_digits; while (cur_digits >= new_digits) { res.emplace_back(int(cur % p[new_digits])); cur /= p[new_digits]; cur_digits -= new_digits; } } res.emplace_back((int)cur); while (!res.empty() && !res.back()) res.pop_back(); return res; } using vll = vector<long long>; static vll karatsubaMultiply(const vll &a, const vll &b) { int n = a.size(); vll res(n + n); if (n <= 32) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) res[i + j] += a[i] * b[j]; return res; } int k = n >> 1; vll a1(a.begin(), a.begin() + k); vll a2(a.begin() + k, a.end()); vll b1(b.begin(), b.begin() + k); vll b2(b.begin() + k, b.end()); vll a1b1 = karatsubaMultiply(a1, b1); vll a2b2 = karatsubaMultiply(a2, b2); for (int i = 0; i < k; i++) a2[i] += a1[i]; for (int i = 0; i < k; i++) b2[i] += b1[i]; vll r = karatsubaMultiply(a2, b2); for (int i = 0; i < (int)a1b1.size(); i++) r[i] -= a1b1[i]; for (int i = 0; i < (int)a2b2.size(); i++) r[i] -= a2b2[i]; for (int i = 0; i < (int)r.size(); i++) res[i + k] += r[i]; for (int i = 0; i < (int)a1b1.size(); i++) res[i] += a1b1[i]; for (int i = 0; i < (int)a2b2.size(); i++) res[i + n] += a2b2[i]; return res; } }; BigInt gcd(const BigInt &x, const BigInt &y) { return y.isZero() ? x : gcd(y, x % y); } BigInt lcm(const BigInt &x, const BigInt &y) { return x / gcd(x, y) * y; } // エラトステネスの篩 // O(n log log n) // Verified: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3452809 vector<bool> eratos(int n) { vector<bool> is_prime(n + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i*i <= n; i++) { if (!is_prime[i])continue; for (int j = i * i; j <= n; j += i) is_prime[j] = false; } 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 % 2)x = x + y % mod; y = y * 2 % mod; b /= 2; } 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 % 2)res = modmul(res, a, mod); a = modmul(a, a, mod); e /= 2; } dump(a, e, mod, res); return res; } // 素数判定(Miller-Rabin primality test) // 2^24程度から // 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; dump(s); while (s % 2 == 0)s /= 2; dump(s); for (int i = 0; i < iteration; i++) { Int a = BigInt(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; dump(tmp); } if (mod != x - 1 && tmp % 2 == 0)return false; } return true; } using Int = BigInt; signed main() { cin.tie(0); ios::sync_with_stdio(false); Int n; cin >> n; if (n < 50) { int N = n.d[0]; 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 -1; }; auto res = bfs(0, 0, (N - 1) / w, (N - 1) % w); dump(res); if (res != -1) { cout << w << endl; break; } } } else { dump(n); for (int w = 8;; w += 2) { if (millerRabinPrimalityTest(Int(1 + w), 5))continue; if (((n - 1) % w) == 0 && millerRabinPrimalityTest(n - w, 5))continue; cout << w << endl; break; } } return 0; }