結果
問題 | No.308 素数は通れません |
ユーザー |
![]() |
提出日時 | 2019-08-20 17:16:33 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 6 ms / 1,000 ms |
コード長 | 1,962 bytes |
コンパイル時間 | 555 ms |
コンパイル使用メモリ | 27,776 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-06 12:39:07 |
合計ジャッジ時間 | 2,828 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 107 |
ソースコード
// yukicoder: No.308 素数は通れません// bal4u 2019.8.20#include <stdio.h>#include <stdlib.h>#include <string.h>typedef __int128_t Bint; // GCC 環境下でないと動かないかも//// 入出力関係#if 1#define gc() getchar_unlocked()#else#define gc() getchar()#endifBint in() { // 非負整数の入力Bint n = 0, c = gc();do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');return n;}//// ミラー–ラビン素数判定法#if 0#define mulmod(a,b,n) (a*b%n)#else#define mod(a,m) ((a)%(m))inline static Bint mulmod(Bint a, Bint b, Bint m) {Bint ans = 0;a = mod(a, m), b = mod(b, m);while (b > 0) {if (b & 1) ans = mod(ans + a, m);a = mod(a << 1, m);b >>= 1;}return ans;}#endifBint modpow(Bint x, Bint p, Bint n) {Bint r = 1;while (p) {if (p & 1) r = mulmod(r, x, n);x = mulmod(x, x, n);p >>= 1;}return r;}//int ptbl[] = { 2, 325, 9375,28178,450775,9780504,1795265022,0 }; // for 64bitsint ptbl[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 41, 0};int miller_rabin(Bint n) {int i, j, b, t; Bint u, x;u = n-1, t = 0; while ((u & 1) == 0) u >>= 1, t++;for (j = 0; ptbl[j]; j++) {if ((b = ptbl[j]) >= n) {b %= n;if (b == 0) return 1; // continue;}x = modpow(b, u, n);if (x == 1 || x == n-1) continue;i = 1; while (1) {if (i++ == t) return 0;x = mulmod(x, x, n);if (x == 1) return 0;if (x == n-1) break;}}return 1;}int isprime(Bint n) {if (n == 2) return 1;if (n == 1 || (n & 1) == 0) return 0;if (n % 5 == 0) return 0;return miller_rabin(n);}int ans[] = {0,1, 2, 3, 3, 5, 5, 7, 7, 7, 7, 11, 11, 13, 13, 7, 7, 17, 8, 19, 19,19, 7, 23,23,23, 8, 8, 8,29, 8, 31, 8, 8, 8, 8, 8, 37, 8, 8, 8,41, 8, 43, 8, 8, 8, 47, 8, 14, 8};int main(){int W; Bint N;N = in();if (N > 50) {W = 8;if (N % 8 == 1 && isprime(N-8)) W = 14;} else W = ans[N];printf("%d\n", W);return 0;}