結果
問題 | No.8030 ミラー・ラビン素数判定法のテスト |
ユーザー | satonakatakumi |
提出日時 | 2021-08-21 11:13:17 |
言語 | C (gcc 12.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,744 bytes |
コンパイル時間 | 458 ms |
コンパイル使用メモリ | 32,512 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-15 02:29:56 |
合計ジャッジ時間 | 903 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
ソースコード
#include <assert.h> #include <stdbool.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> typedef int8_t i8; typedef int16_t i16; typedef int32_t i32; typedef int64_t i64; typedef __int128_t i128; typedef uint8_t u8; typedef uint16_t u16; typedef uint32_t u32; typedef uint64_t u64; typedef __uint128_t u128; typedef struct Montgomery64 { u64 m, r, n2; u64 x; } m64; u64 MR(m64 m_, u128 b) { return (b + (u128)((u64)b * m_.r) * m_.m) >> 64; } u64 RM(m64 m_) { u64 y = MR(m_, m_.x); return y >= m_.m ? y - m_.m : y; } m64 make_montgomery(u64 n, u64 mod) { m64 result; assert(mod != 0); assert((mod & 1) != 0); result.m = mod; result.n2 = -(u128)(mod) % mod; result.r = mod; for (int _ = 0; _ < 5; _++) result.r *= 2 - result.m * result.r; result.r = -result.r; result.x = MR(result, (u128)n * result.n2); return result; } m64 plusmod(m64 p, m64 q) { p.x += q.x - (q.m << 1); p.x = ((i64)p.x < 0 ? p.x + (p.m << 1) : p.x); return p; } m64 minusmod(m64 p, m64 q) { p.x -= q.x; p.x = ((i64)p.x < 0 ? p.x + (p.m << 1) : p.x); return p; } m64 mulmod(m64 p, m64 q) { p.x = MR(p, (u128)p.x * q.x); return p; } m64 powmod(m64 p, u64 n) { m64 y = make_montgomery(1, p.m); m64 z = p; for (; n; n >>= 1, z = mulmod(z, z)) if (n & 1) y = mulmod(y, z); return y; } bool eq(m64 p, m64 q) { return (p.x >= p.m ? p.x - p.m : p.x) == (q.x >= q.m ? q.x - q.m : q.x); } bool not_eq(m64 p, m64 q) { return !eq(p, q); } bool is_prime(const u64 n) { if (n == 2 || n == 3 || n == 5 || n == 7) return true; if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) return false; if (n < 121) return n > 1; const u64 m = n - 1; const u64 d = m >> __builtin_ctzll(m); const m64 one = make_montgomery(1, n), minus_one = make_montgomery(m, n); const u64 check1[3] = {2, 7, 61}; const u64 check2[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; if (n < (1ull << 32)) { for (int i = 0; i < 3; i++) { m64 a = make_montgomery(check1[i], n); m64 y = powmod(a, d); u64 t = d; while (not_eq(y, one) && not_eq(y, minus_one) && t != m) y = mulmod(y, y), t <<= 1; if (not_eq(y, minus_one) && t % 2 == 0) return false; } } else { for (int i = 0; i < 7; i++) { if (n <= check2[i]) return true; m64 a = make_montgomery(check2[i], n); m64 y = powmod(a, d); u64 t = d; while (not_eq(y, one) && not_eq(y, minus_one) && t != m) y = mulmod(y, y), t <<= 1; if (not_eq(y, minus_one) && t % 2 == 0) return false; } } return true; } int main() { int i, n; scanf("%d", &n); u64 u; for (i = 0; i < n; i++) { scanf("%lu", &u); printf("%lu ", u); if (is_prime(u)) printf("1\n"); else printf("0\n"); } return 0; }