#64446 (C++11) No.308 素数は通れません

提出ソース

結果

問題	No.308 素数は通れません
ユーザー	moti
提出日時	2015-12-10 12:30:01
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	23 ms / 1,000 ms
コード長	6,714 bytes
コンパイル時間	973 ms
コンパイル使用メモリ	112,784 KB
実行使用メモリ	4,384 KB
最終ジャッジ日時	2023-08-18 13:24:06
合計ジャッジ時間	4,275 ms
ジャッジサーバーID （参考情報）	judge12 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	AC	1 ms 4,384 KB
testcase_04	AC	2 ms 4,380 KB
testcase_05	AC	2 ms 4,380 KB
testcase_06	AC	2 ms 4,376 KB
testcase_07	AC	1 ms 4,380 KB
testcase_08	AC	2 ms 4,376 KB
testcase_09	AC	2 ms 4,380 KB
testcase_10	AC	2 ms 4,380 KB
testcase_11	AC	1 ms 4,380 KB
testcase_12	AC	2 ms 4,380 KB
testcase_13	AC	2 ms 4,380 KB
testcase_14	AC	2 ms 4,376 KB
testcase_15	AC	2 ms 4,376 KB
testcase_16	AC	2 ms 4,376 KB
testcase_17	AC	1 ms 4,380 KB
testcase_18	AC	2 ms 4,376 KB
testcase_19	AC	1 ms 4,376 KB
testcase_20	AC	1 ms 4,380 KB
testcase_21	AC	2 ms 4,376 KB
testcase_22	AC	1 ms 4,376 KB
testcase_23	AC	2 ms 4,380 KB
testcase_24	AC	2 ms 4,380 KB
testcase_25	AC	2 ms 4,380 KB
testcase_26	AC	1 ms 4,380 KB
testcase_27	AC	1 ms 4,376 KB
testcase_28	AC	2 ms 4,380 KB
testcase_29	AC	2 ms 4,376 KB
testcase_30	AC	1 ms 4,380 KB
testcase_31	AC	1 ms 4,376 KB
testcase_32	AC	1 ms 4,376 KB
testcase_33	AC	2 ms 4,376 KB
testcase_34	AC	2 ms 4,380 KB
testcase_35	AC	2 ms 4,376 KB
testcase_36	AC	2 ms 4,376 KB
testcase_37	AC	2 ms 4,380 KB
testcase_38	AC	1 ms 4,376 KB
testcase_39	AC	2 ms 4,376 KB
testcase_40	AC	1 ms 4,376 KB
testcase_41	AC	1 ms 4,376 KB
testcase_42	AC	2 ms 4,376 KB
testcase_43	AC	1 ms 4,380 KB
testcase_44	AC	1 ms 4,380 KB
testcase_45	AC	2 ms 4,376 KB
testcase_46	AC	1 ms 4,380 KB
testcase_47	AC	1 ms 4,380 KB
testcase_48	AC	1 ms 4,380 KB
testcase_49	AC	2 ms 4,376 KB
testcase_50	AC	1 ms 4,376 KB
testcase_51	AC	2 ms 4,380 KB
testcase_52	AC	2 ms 4,376 KB
testcase_53	AC	1 ms 4,380 KB
testcase_54	AC	1 ms 4,380 KB
testcase_55	AC	1 ms 4,376 KB
testcase_56	AC	2 ms 4,376 KB
testcase_57	AC	1 ms 4,380 KB
testcase_58	AC	2 ms 4,376 KB
testcase_59	AC	1 ms 4,376 KB
testcase_60	AC	1 ms 4,376 KB
testcase_61	AC	1 ms 4,376 KB
testcase_62	AC	1 ms 4,380 KB
testcase_63	AC	1 ms 4,376 KB
testcase_64	AC	2 ms 4,376 KB
testcase_65	AC	2 ms 4,376 KB
testcase_66	AC	1 ms 4,376 KB
testcase_67	AC	2 ms 4,376 KB
testcase_68	AC	2 ms 4,380 KB
testcase_69	AC	1 ms 4,376 KB
testcase_70	AC	1 ms 4,376 KB
testcase_71	AC	2 ms 4,380 KB
testcase_72	AC	2 ms 4,376 KB
testcase_73	AC	1 ms 4,380 KB
testcase_74	AC	2 ms 4,376 KB
testcase_75	AC	2 ms 4,376 KB
testcase_76	AC	2 ms 4,376 KB
testcase_77	AC	2 ms 4,376 KB
testcase_78	AC	1 ms 4,380 KB
testcase_79	AC	1 ms 4,376 KB
testcase_80	AC	3 ms 4,380 KB
testcase_81	AC	4 ms 4,376 KB
testcase_82	AC	2 ms 4,376 KB
testcase_83	AC	2 ms 4,376 KB
testcase_84	AC	5 ms 4,380 KB
testcase_85	AC	1 ms 4,376 KB
testcase_86	AC	6 ms 4,376 KB
testcase_87	AC	8 ms 4,380 KB
testcase_88	AC	2 ms 4,380 KB
testcase_89	AC	2 ms 4,380 KB
testcase_90	AC	11 ms 4,376 KB
testcase_91	AC	2 ms 4,376 KB
testcase_92	AC	1 ms 4,376 KB
testcase_93	AC	1 ms 4,380 KB
testcase_94	AC	2 ms 4,376 KB
testcase_95	AC	2 ms 4,380 KB
testcase_96	AC	1 ms 4,376 KB
testcase_97	AC	1 ms 4,380 KB
testcase_98	AC	1 ms 4,376 KB
testcase_99	AC	2 ms 4,380 KB
testcase_100	AC	2 ms 4,380 KB
testcase_101	AC	23 ms 4,376 KB
testcase_102	AC	2 ms 4,376 KB
testcase_103	AC	1 ms 4,380 KB
testcase_104	AC	2 ms 4,376 KB
testcase_105	AC	1 ms 4,380 KB
testcase_106	AC	2 ms 4,380 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// 乗算は専用に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;
}

yukicoder

結果

テストケース

ソースコード