結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | bal4u |
提出日時 | 2019-05-12 19:42:01 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 232 ms / 9,973 ms |
コード長 | 1,980 bytes |
コンパイル時間 | 437 ms |
コンパイル使用メモリ | 31,616 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-16 23:14:17 |
合計ジャッジ時間 | 1,483 ms |
ジャッジサーバーID (参考情報) |
judge1 / 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 | AC | 133 ms
5,248 KB |
testcase_05 | AC | 125 ms
5,248 KB |
testcase_06 | AC | 50 ms
5,248 KB |
testcase_07 | AC | 50 ms
5,248 KB |
testcase_08 | AC | 48 ms
5,248 KB |
testcase_09 | AC | 232 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.12 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++); } // 文字列の表示 //// ラビン素数テスト #define mulmod128(a,b,n) ((__int128_t)a*b % n) ull powmod(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; } unsigned xorshift(int id) { static unsigned y = 2463534242; y = y ^ (y << 13), y = y ^ (y >> 17), y = y ^ (y << 5); return y; } ull gcd(ull a, ull b) { ull r; while (b != 0) r = a % b, a = b, b = r; return a; } 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 < 6; j++) { do b = xorshift(j) % n; while (gcd(b, n) > 1); x = powmod(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) { if (n <= 1) return 0; if (n == 2 || n == 3) return 1; if ((n & 1) == 0) return 0; return suspect(n); } char s[25]; int main() { int n; long long x; n = in(); while (n--) { ins(s), outs(s), pc(' '); pc('0' + miller_rabin(s2ll(s))), pc('\n'); } return 0; }