結果

問題 No.308 素数は通れません
ユーザー motimoti
提出日時 2015-12-10 12:30:01
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 22 ms / 1,000 ms
コード長 6,714 bytes
コンパイル時間 1,106 ms
コンパイル使用メモリ 116,560 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-05-05 18:38:56
合計ジャッジ時間 3,518 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 1 ms
5,376 KB
testcase_15 AC 1 ms
5,376 KB
testcase_16 AC 1 ms
5,376 KB
testcase_17 AC 1 ms
5,376 KB
testcase_18 AC 1 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 1 ms
5,376 KB
testcase_21 AC 1 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 1 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 1 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 1 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 1 ms
5,376 KB
testcase_32 AC 1 ms
5,376 KB
testcase_33 AC 1 ms
5,376 KB
testcase_34 AC 1 ms
5,376 KB
testcase_35 AC 1 ms
5,376 KB
testcase_36 AC 1 ms
5,376 KB
testcase_37 AC 1 ms
5,376 KB
testcase_38 AC 1 ms
5,376 KB
testcase_39 AC 2 ms
5,376 KB
testcase_40 AC 2 ms
5,376 KB
testcase_41 AC 2 ms
5,376 KB
testcase_42 AC 2 ms
5,376 KB
testcase_43 AC 2 ms
5,376 KB
testcase_44 AC 2 ms
5,376 KB
testcase_45 AC 1 ms
5,376 KB
testcase_46 AC 1 ms
5,376 KB
testcase_47 AC 2 ms
5,376 KB
testcase_48 AC 1 ms
5,376 KB
testcase_49 AC 1 ms
5,376 KB
testcase_50 AC 1 ms
5,376 KB
testcase_51 AC 1 ms
5,376 KB
testcase_52 AC 1 ms
5,376 KB
testcase_53 AC 2 ms
5,376 KB
testcase_54 AC 1 ms
5,376 KB
testcase_55 AC 2 ms
5,376 KB
testcase_56 AC 2 ms
5,376 KB
testcase_57 AC 2 ms
5,376 KB
testcase_58 AC 2 ms
5,376 KB
testcase_59 AC 2 ms
5,376 KB
testcase_60 AC 2 ms
5,376 KB
testcase_61 AC 1 ms
5,376 KB
testcase_62 AC 2 ms
5,376 KB
testcase_63 AC 1 ms
5,376 KB
testcase_64 AC 2 ms
5,376 KB
testcase_65 AC 1 ms
5,376 KB
testcase_66 AC 2 ms
5,376 KB
testcase_67 AC 1 ms
5,376 KB
testcase_68 AC 1 ms
5,376 KB
testcase_69 AC 1 ms
5,376 KB
testcase_70 AC 2 ms
5,376 KB
testcase_71 AC 2 ms
5,376 KB
testcase_72 AC 2 ms
5,376 KB
testcase_73 AC 1 ms
5,376 KB
testcase_74 AC 1 ms
5,376 KB
testcase_75 AC 1 ms
5,376 KB
testcase_76 AC 2 ms
5,376 KB
testcase_77 AC 1 ms
5,376 KB
testcase_78 AC 2 ms
5,376 KB
testcase_79 AC 1 ms
5,376 KB
testcase_80 AC 3 ms
5,376 KB
testcase_81 AC 4 ms
5,376 KB
testcase_82 AC 2 ms
5,376 KB
testcase_83 AC 2 ms
5,376 KB
testcase_84 AC 4 ms
5,376 KB
testcase_85 AC 2 ms
5,376 KB
testcase_86 AC 5 ms
5,376 KB
testcase_87 AC 7 ms
5,376 KB
testcase_88 AC 2 ms
5,376 KB
testcase_89 AC 2 ms
5,376 KB
testcase_90 AC 9 ms
5,376 KB
testcase_91 AC 1 ms
5,376 KB
testcase_92 AC 1 ms
5,376 KB
testcase_93 AC 1 ms
5,376 KB
testcase_94 AC 1 ms
5,376 KB
testcase_95 AC 2 ms
5,376 KB
testcase_96 AC 2 ms
5,376 KB
testcase_97 AC 2 ms
5,376 KB
testcase_98 AC 2 ms
5,376 KB
testcase_99 AC 2 ms
5,376 KB
testcase_100 AC 2 ms
5,376 KB
testcase_101 AC 22 ms
5,376 KB
testcase_102 AC 2 ms
5,376 KB
testcase_103 AC 2 ms
5,376 KB
testcase_104 AC 1 ms
5,376 KB
testcase_105 AC 2 ms
5,376 KB
testcase_106 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

// 乗算は専用にmodを取るmulmodなどを使わないと __int128_t では mod_pow あたりで system_test1.txt でオーバーフローして死んでるっぽい。
// 0_small_32.txt などの小さいケースは BFS した方がいいかもしれない(代わりに素数を小さい方からあてがっていく判定法を用いた)

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
#include <numeric>
#include <bitset>

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define minimize(a, x) a = std::min(a, x)
#define maximize(a, x) a = std::max(a, x)


int const inf = 1<<29;
typedef __int128_t ll;

#include <random>

namespace math { namespace integer {

template<class value_type> value_type mod_mul(value_type x, value_type k, value_type m) { if(k == 0) { return 0; } if(k % 2 == 0) { return mod_mul((x+x) % m, k/2, m); } else { return (x + mod_mul(x, k-1, m)) % m; } }
template<class value_type> value_type mod_pow(value_type x, value_type n, value_type mod) { if(n == 0) { return 1; } if(n % 2 == 0) { return mod_pow(mod_mul(x, x, mod) % mod, n / 2, mod); } else { return mod_mul(x, mod_pow(x, n - 1, mod), mod); } }

}}

using namespace math::integer;

namespace math { namespace prime {

namespace detail {

template <class I>
bool check_small_factors(const I& n) {
   static const uint32_t small_factors1[] = {
      3u, 5u, 7u, 11u, 13u, 17u, 19u, 23u };
   static const uint32_t pp1 = 223092870u;

   uint32_t m1 = n % pp1;

   for(unsigned i = 0; i < sizeof(small_factors1) / sizeof(small_factors1[0]); ++i) {
     if(m1 % small_factors1[i] == 0) { return false; }
   }

   static const uint32_t small_factors2[] = { 29u, 31u, 37u, 41u, 43u, 47u };
   static const uint32_t pp2 = 2756205443u;

   m1 = n % pp2;

   for(unsigned i = 0; i < sizeof(small_factors2) / sizeof(small_factors2[0]); ++i) {
     if(m1 % small_factors2[i] == 0) { return false; }
   }

   static const uint32_t small_factors3[] = { 53u, 59u, 61u, 67u, 71u };
   static const uint32_t pp3 = 907383479u;

   m1 = n % pp3;

   for(unsigned i = 0; i < sizeof(small_factors3) / sizeof(small_factors3[0]); ++i) {
     if(m1 % small_factors3[i] == 0) { return false; }
   }

   static const uint32_t small_factors4[] = { 73u, 79u, 83u, 89u, 97u };
   static const uint32_t pp4 = 4132280413u;

   m1 = n % pp4;

   for(unsigned i = 0; i < sizeof(small_factors4) / sizeof(small_factors4[0]); ++i) {
     if(m1 % small_factors4[i] == 0) { return false; }
   }

   static const uint32_t small_factors5[6][4] = {
      { 101u, 103u, 107u, 109u },
      { 113u, 127u, 131u, 137u },
      { 139u, 149u, 151u, 157u },
      { 163u, 167u, 173u, 179u },
      { 181u, 191u, 193u, 197u },
      { 199u, 211u, 223u, 227u }
   };
   static const uint32_t pp5[6] = 
   { 
      121330189u, 
      113u * 127u * 131u * 137u, 
      139u * 149u * 151u * 157u,
      163u * 167u * 173u * 179u,
      181u * 191u * 193u * 197u,
      199u * 211u * 223u * 227u
   };

   for(unsigned k = 0; k < sizeof(pp5) / sizeof(*pp5); ++k) {
     m1 = n % pp5[k];

     for(unsigned i = 0; i < 4; ++i) {
       if(m1 % small_factors5[k][i] == 0) { return false; }
     }
   }
   return true;
}

inline bool is_small_prime(unsigned n) {
   static const unsigned char p[] = {
      3u, 5u, 7u, 11u, 13u, 17u, 19u, 23u, 29u, 31u, 
      37u, 41u, 43u, 47u, 53u, 59u, 61u, 67u, 71u, 73u, 
      79u, 83u, 89u, 97u, 101u, 103u, 107u, 109u, 113u, 
      127u, 131u, 137u, 139u, 149u, 151u, 157u, 163u, 
      167u, 173u, 179u, 181u, 191u, 193u, 197u, 199u, 
      211u, 223u, 227u
   };
   for(unsigned i = 0; i < sizeof(p) / sizeof(*p); ++i) {
      if(n == p[i]) { return true; }
   }
   return false;
}

template<class I> bool cast_to_unsigned(I n) { return static_cast<unsigned>(n % std::numeric_limits<unsigned>::max()); }

} // namespace detail

template<class I, class Engine>
bool miller_rabin_test(const I& n, unsigned trials, Engine& gen) {

  typedef I number_type;

  if((n % 2) == 0) { return false; }
  if(n <= 227) {
    return detail::is_small_prime(detail::cast_to_unsigned(n));
  }

  if(!detail::check_small_factors(n)) { return false; }

  number_type nm1 = n - 1;

  // Fermat test
  number_type q(228), x, y;
  x = mod_pow(q, nm1, n);
  if(x != 1u) { return false; }

  q = n - 1;
  while(!(q & 1)) q >>= 1;

  std::uniform_int_distribution<number_type> dist(1, n - 2);
  
  // Execute miller-rabin-test trials:
  for(unsigned i = 0; i < trials; ++i) {
    x = mod_mul(dist(gen), dist(gen), n - 2) + 1;
    number_type t = q;
    y = mod_pow(x, t, n);
    while(t != n-1 && y != 1 && y != n-1) {
      y = mod_mul(y, y, n);
      t <<= 1;
    }
    if(y != n-1 && (t & 1) == 0) {
      return false;
    }
  }

  return true; // probably prime

}

template<class I>
bool suspect(const I& a, I s, I d, I n) {
  ll x = mod_pow(a, d, n);
  if (x == 1) return true;
  for(int r = 0; r < s; ++r) {
    if(x == n - 1) return true;
    x = mod_mul(x, x, n);
  }
  return false;
}

bool miller_rabin_test2(ll n) {
  if(n <= 1 || (n > 2 && n % 2 == 0)) { return false; }
  vector<int> test = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, -1 };
  ll d = n - 1, s = 0;
  while(d % 2 == 0) { s ++; d /= 2; }
  for(int i = 0; test[i] < n && test[i] != -1; i++) {
    if(!suspect((ll)test[i], s, d, n)) { return false; }
  }
  return true;
}


template<class I>
bool miller_rabin_test(const I& n, int type = 0) {
  if(type == 0) {
    return miller_rabin_test2(n);
  }
  else {
    static std::mt19937 gen;
    return miller_rabin_test(n, 25, gen);
  }
}

}}

map<ll, int> mp = {
  {4,3}, 
  {6,5}, 
  {8,7}, 
  {9,7}, 
  {10,7}, 
  {12,11}, 
  {14,13}, 
  {15,7}, 
  {16,7}, 
  {18,8}, 
  {20,19}, 
  {21,19}, 
  {22,7}, 
  {24,23}, 
  {25,23},
};

int main() {

  string s; cin >> s;
  ll N = 0;
  rep(i, s.size()) {
    N = N * 10;
    N = N + (s[i] - '0');
  }

  if(mp.find(N) != mp.end()) {
    cout << mp[N] << endl;
    exit(0);
  }

  if((N % 8 == 1) && math::prime::miller_rabin_test(N - 8)) {
    cout << 14 << endl;
  }
  else {
    cout << 8 << endl;
  }

  return 0;
}
0