結果
| 問題 | No.308 素数は通れません |
| コンテスト | |
| ユーザー |
 moti
|
| 提出日時 | 2015-12-10 12:18:38 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,582 bytes |
| 記録 | |
| コンパイル時間 | 1,420 ms |
| コンパイル使用メモリ | 119,828 KB |
| 実行使用メモリ | 6,948 KB |
| 最終ジャッジ日時 | 2024-09-15 07:28:10 |
| 合計ジャッジ時間 | 4,066 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge6 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 106 WA * 1 |
ソースコード
#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()); }
struct xor128 {
unsigned x,y,z,w;
xor128(): x(89165727), y(157892372), z(7777777), w(757328) {}
unsigned next() {
unsigned t=x^(x<<11);
x=y;y=z;z=w;
return w=w^(w>>19)^t^(t>>8);
}
unsigned next(unsigned k) {
return next()%k;
}
} rndgen;
}
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 = (number_type)dist(gen);
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 = 1) {
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;
}