結果
| 問題 | No.3030 ミラー・ラビン素数判定法のテスト |
| ユーザー |
 Jashinchan
|
| 提出日時 | 2022-08-29 13:15:55 |
| 言語 | C (gcc 12.3.0) |
| 結果 |
AC
|
| 実行時間 | 16 ms / 9,973 ms |
| コード長 | 4,789 bytes |
| コンパイル時間 | 447 ms |
| コンパイル使用メモリ | 34,144 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-04-28 10:01:01 |
| 合計ジャッジ時間 | 1,006 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
5,248 KB |
| testcase_01 | AC | 1 ms
5,376 KB |
| testcase_02 | AC | 1 ms
5,376 KB |
| testcase_03 | AC | 1 ms
5,376 KB |
| testcase_04 | AC | 9 ms
5,376 KB |
| testcase_05 | AC | 10 ms
5,376 KB |
| testcase_06 | AC | 8 ms
5,376 KB |
| testcase_07 | AC | 8 ms
5,376 KB |
| testcase_08 | AC | 8 ms
5,376 KB |
| testcase_09 | AC | 16 ms
5,376 KB |
コンパイルメッセージ
main.c: In function 'in':
main.c:91:51: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
91 | uint64_t in(void) { uint64_t c, x = 0; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return x; }
| ^~~~~~~~~~~~~~~~
main.c: In function 'out':
main.c:92:99: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration]
92 | void out(uint64_t x) { if (x >= 10) out((((__uint128_t)x * 14757395258967641293ull) >> 3) >> 64); putchar_unlocked(x - ((((__uint128_t)x * 14757395258967641293ull) >> 3) >> 64) * 10 + 48); }
| ^~~~~~~~~~~~~~~~
ソースコード
#include <stdint.h>
#include <stdio.h>
int jacobi_symbol(int64_t a, uint64_t n) { uint64_t t; int j = 1; while (a) { if (a < 0) { a = -a; if ((n & 3) == 3) j = -j; } int s = __builtin_ctzll(a); a >>= s; if (((n & 7) == 3 || (n & 7) == 5) && (s & 1)) { j = -j; } if ((a & n & 3) == 3) { j = -j; } t = a; a = n; n = t; a %= n; if ((uint64_t)(a) > n / 2) { a -= n; } } return n == 1 ? j : 0; }
uint64_t remain_sqrt(uint64_t x) { if (x == 0) { return 0; } uint32_t lz = __builtin_clzll(x); uint64_t n = 32 - (lz >> 1); uint64_t s = (lz >> 1) << 1; uint64_t t = n << 1; __uint128_t a = (__uint128_t)x; __uint128_t b = ((__uint128_t)1ull << 62) >> s; __uint128_t c = ((__uint128_t)1ull << 64) >> s; __uint128_t d = (((__uint128_t)1ull << 64) - 1) >> s; __uint128_t e = ((((__uint128_t)1ull << 64) - 1) << 65) >> s; for (int _ = 0; _ < n; ++_) { if (a >= b) { a -= b; b = ((b + b) & e) + c + (b & d); } else { b = ((b + b) & e) + (b & d); } a <<= 2; } return a >> t; }
uint64_t mr64(__uint128_t A, uint64_t n, uint64_t ninv) { uint64_t y = (uint64_t)(A >> 64) - (uint64_t)(((__uint128_t)((uint64_t)A * ninv) * n) >> 64); return (int64_t)y < 0 ? y + n : y; }
uint64_t to_m64(uint64_t a, uint64_t n, uint64_t ninv, uint64_t r2) { return mr64((__uint128_t)a * r2, n, ninv); }
uint64_t from_m64(uint64_t mra, uint64_t n, uint64_t ninv) { return mr64((__uint128_t)mra, n, ninv); }
uint64_t add_m64(uint64_t mra, uint64_t mrb, uint64_t n) { return mra >= n - mrb ? mra + mrb - n : mra + mrb; }
uint64_t sub_m64(uint64_t mra, uint64_t mrb, uint64_t n) { return mra >= mrb ? mra - mrb : mra + n - mrb; }
uint64_t min_m64(uint64_t mra, uint64_t n) { return sub_m64(0, mra, n); }
uint64_t mul_m64(uint64_t mra, uint64_t mrb, uint64_t n, uint64_t ninv) { return mr64((__uint128_t)mra * mrb, n, ninv); }
uint64_t twice_m64(uint64_t mra, uint64_t n) { return (mra <<= 1) >= n ? (mra - n) : mra; }
uint64_t half_m64(uint64_t mra, uint64_t n) { return (mra & 1) ? ((mra + n) >> 1) : (mra >> 1); }
int is_prime(uint64_t n)
{
{
if (~n & 1) return n == 2;
if (n < 4) return n == 3;
}
uint64_t r = (uint64_t)-1ull % n + 1;
uint64_t r2 = (__uint128_t)(__int128_t)-1 % n + 1;
uint64_t ninv = n;
for (int _ = 0; _ < 5; ++_) ninv *= 2 - ninv * n;
{
uint64_t d = (n - 1) << __builtin_clzll(n - 1);
uint64_t t = twice_m64(r, n);
for (d <<= 1; d; d <<= 1)
{
t = mul_m64(t, t, n, ninv);
if (d >> 63) t = twice_m64(t, n);
}
if (t != r)
{
uint64_t x = (n - 1) & -(n - 1);
uint64_t rev = min_m64(r ,n);
for (x >>= 1; t != rev; x >>= 1)
{
if (x == 0)
return 0;
t = mul_m64(t, t, n, ninv);
}
}
}
{
int64_t D = 5;
for (int i = 0; jacobi_symbol(D, n) != -1 && i < 64; ++i)
{
if (i == 32 && remain_sqrt(n) == 0) return 0;
if (i & 1) D -= 2;
else D += 2;
D = -D;
}
uint64_t Q = to_m64(((D < 0) ? ((1 - D) / 4 % n) : (n - (D - 1) / 4 % n)), n, ninv, r2);
uint64_t u = r, v = r, Qn = Q;
uint64_t k = (n + 1) << __builtin_clzll(n + 1);
D %= (int64_t)n;
D = to_m64(((D < 0) ? ((int64_t)n + D) : D), n, ninv ,r2);
for (k <<= 1; k; k <<= 1) {
u = mul_m64(u, v, n, ninv);
v = sub_m64(mul_m64(v, v, n, ninv), add_m64(Qn, Qn, n), n);
Qn = mul_m64(Qn, Qn, n, ninv);
if (k >> 63) {
uint64_t uu = add_m64(u, v, n);
uu = half_m64(uu, n);
v = add_m64(mul_m64(D, u, n, ninv), v, n);
v = half_m64(v, n);
u = uu;
Qn = mul_m64(Qn, Q, n, ninv);
}
}
if (u == 0 || v == 0)
return 1;
uint64_t x = (n + 1) & ~n;
for (x >>= 1; x; x >>= 1)
{
u = mul_m64(u, v, n, ninv);
v = sub_m64(mul_m64(v, v, n, ninv), add_m64(Qn, Qn, n), n);
if (v == 0)
return 1;
Qn = mul_m64(Qn, Qn, n, ninv);
}
}
return 0;
}
uint64_t in(void) { uint64_t c, x = 0; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return x; }
void out(uint64_t x) { if (x >= 10) out((((__uint128_t)x * 14757395258967641293ull) >> 3) >> 64); putchar_unlocked(x - ((((__uint128_t)x * 14757395258967641293ull) >> 3) >> 64) * 10 + 48); }
int main(void)
{
uint64_t Q = in();
while (Q--) {
uint64_t x = in();
out(x);
putchar_unlocked(' ');
out(is_prime(x));
putchar_unlocked('\n');
}
return 0;
}