結果
問題 | No.8030 ミラー・ラビン素数判定法のテスト |
ユーザー | Ryuhei Mori |
提出日時 | 2017-10-27 20:45:45 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 31 ms / 9,973 ms |
コード長 | 2,301 bytes |
コンパイル時間 | 387 ms |
コンパイル使用メモリ | 31,232 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-16 23:03:39 |
合計ジャッジ時間 | 921 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | AC | 21 ms
5,248 KB |
testcase_05 | AC | 19 ms
5,248 KB |
testcase_06 | AC | 12 ms
5,248 KB |
testcase_07 | AC | 13 ms
5,248 KB |
testcase_08 | AC | 12 ms
5,248 KB |
testcase_09 | AC | 31 ms
5,248 KB |
ソースコード
#include <stdio.h> #include <stdint.h> typedef unsigned __int128 uint128_t; void ex_gcd(uint64_t y, uint64_t *b){ int i; uint64_t u, v; u = 1; v = 0; uint64_t x = 1LL<<63; for(i=0;i<64;i++){ if(u&1){ u = (u + y) / 2; v = v/2 + x; } else { u >>= 1; v >>= 1; } } *b = v; } uint64_t MR(uint128_t x, uint64_t m, uint64_t n){ uint64_t z = ((uint128_t) ((uint64_t) x * m) * n + x) >> 64; return z < n ? z : z - n; } uint64_t RM(uint64_t x, uint64_t r2, uint64_t m, uint64_t n){ return MR((uint128_t) r2 * x, m, n); } uint64_t modpow64(uint64_t a, uint64_t k, uint64_t m, uint64_t n, uint64_t one){ uint64_t r; for(r=one;k;k/=2){ if(k&1) r = MR((uint128_t)r*a, m, n); a = MR((uint128_t) a*a, m, n); } return r; } uint32_t modpow32(uint32_t a, uint32_t k, uint32_t n){ uint32_t r; for(r=1;k;k/=2){ if(k&1) r = (uint64_t)r*a%n; a = (uint64_t) a*a%n; } return r; } const uint32_t as32[] = {2, 7, 61}; int is_prime32(uint32_t n){ int i, j, r; uint32_t d; if(n <= 1) return 0; if(n <= 3) return 1; if(!(n & 1)) return 0; r = __builtin_ctz(n-1); d = (n-1) >> r; for(i=0;i<3;i++){ uint32_t a = as32[i] % n; if(a == 0) return 1; uint32_t t = modpow32(a, d, n); if(t == 1) continue; for(j=0;t!=n-1;j++){ if(j == r-1) return 0; t = (uint64_t) t * t % n; if(t == 1) return 0; } } return 1; } const uint64_t as64[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; int is_prime64(uint64_t n){ int i, j, r; uint64_t d, one, mone, r2, m; if(n <= 1) return 0; if(n <= 3) return 1; if(!(n & 1)) return 0; if(n < (1L << 32)) is_prime32(n); r = __builtin_ctzll(n-1); d = (n-1) >> r; ex_gcd(n, &m); one = -1UL % n + 1; mone = n - one; r2 = (uint128_t) one * one % n; for(i=0;i<7;i++){ uint64_t a = RM(as64[i], r2, m, n); if(a == 0) return 1; uint64_t t = modpow64(a, d, m, n, one); if(t == one) continue; for(j=0;t!=mone;j++){ if(j == r-1) return 0; t = MR((uint128_t) t * t, m, n); if(t == one) return 0; } } return 1; } int main(){ int i, n; scanf("%d", &n); for(i=0;i<n;i++){ uint64_t n; scanf("%ld", &n); printf("%ld %d\n", n, is_prime64(n)); } return 0; }