結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | bal4u |
提出日時 | 2019-05-18 16:16:54 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 221 ms / 9,973 ms |
コード長 | 2,272 bytes |
コンパイル時間 | 371 ms |
コンパイル使用メモリ | 31,232 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-16 23:15:36 |
合計ジャッジ時間 | 1,534 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 124 ms
5,248 KB |
testcase_05 | AC | 118 ms
5,248 KB |
testcase_06 | AC | 49 ms
5,248 KB |
testcase_07 | AC | 50 ms
5,248 KB |
testcase_08 | AC | 46 ms
5,248 KB |
testcase_09 | AC | 221 ms
5,248 KB |
コンパイルメッセージ
main.c: In function 'in': main.c:12:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration] 12 | #define gc() getchar_unlocked() | ^~~~~~~~~~~~~~~~ main.c:20:24: note: in expansion of macro 'gc' 20 | int n = 0, c = gc(); | ^~ main.c: In function 'outs': main.c:13:15: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration] 13 | #define pc(c) putchar_unlocked(c) | ^~~~~~~~~~~~~~~~ main.c:37:33: note: in expansion of macro 'pc' 37 | void outs(char *s) { while (*s) pc(*s++); } // 文字列の表示 | ^~
ソースコード
// yukicoder 3030 ミラー・ラビン素数判定法のテスト // 2019.5.18 bal4u #include <stdio.h> #include <stdlib.h> typedef long long ll; typedef unsigned long long ull; //// 高速入出力 #if 1 #define gc() getchar_unlocked() #define pc(c) putchar_unlocked(c) #else #define gc() getchar() #define pc(c) putchar(c) #endif int in() { // 非負整数の入力 int n = 0, c = gc(); do n = 10 * n + (c & 0xf), c = gc(); while (c >= '0'); return n; } void ins(char *s) { // 文字列の入力 スペース以下の文字で入力終了 do *s = gc(); while (*s++ > ' '); *(s-1) = 0; } long long s2ll(char *s) { // 非負整数への変換 long long n = 0; while (*s) n = 10*n + (*s++ & 0xf); return n; } void outs(char *s) { while (*s) pc(*s++); } // 文字列の表示 //// ラビン素数テスト #if 1 #define mulmod128(a,b,n) ((__int128_t)a*b % n) #else #define mod(a,m) ((a)%(m)) ull mulmod128(ull a, ull b, ull m) { ull 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; } #endif #if 0 ull modpow(ull a, ull k, ull n) { ull bit = 0x2000000000000000LL, p = 1; while (bit) { if (p > 1) p = mulmod128(p, p, n); if (k & bit) p = mulmod128(p, a, n); bit >>= 1; } return p; } #else ull modpow(ull x, ull p, ull n) { ull r = 1; while (p) { if (p & 1) r = mulmod128(r, x, n); x = mulmod128(x, x, n); p >>= 1; } return r; } #endif int ptbl[] = { 2,325,9375,28178,450775,9780504,1795265022, 0 }; int suspect(ull n) { int i, j, b; ull t, u, x; u = n-1, t = 0; while ((u & 1) == 0) u >>= 1, t++; for (j = 0; j < 7; j++) { if ((b = ptbl[j]) >= n) b %= n; if (b == 0) continue; x = modpow(b, u, n); if (x == 1 || x == n-1) continue; for (i = 1; i < t; i++) { x = mulmod128(x, x, n); if (x == 1) return 0; if (x == n-1) break; } if (i == t) return 0; } return 1; } int miller_rabin(ull n) { int p[10] = { 0,0,1,1,0,1,0,1,0,0 }; if (n < 10) return p[n]; if ((n & 1) == 0) return 0; if (n % 5 == 0) return 0; return suspect(n); } int main() { int n; long long x; char s[25]; n = in(); while (n--) { ins(s), outs(s), pc(' '); pc('0' + miller_rabin(s2ll(s))), pc('\n'); } return 0; }