結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー 👑 MizarMizar
提出日時 2022-09-02 16:23:39
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 229 ms / 9,973 ms
コード長 2,474 bytes
コンパイル時間 271 ms
コンパイル使用メモリ 34,304 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-28 10:05:19
合計ジャッジ時間 1,366 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 132 ms
5,376 KB
testcase_05 AC 129 ms
5,376 KB
testcase_06 AC 51 ms
5,376 KB
testcase_07 AC 51 ms
5,376 KB
testcase_08 AC 51 ms
5,376 KB
testcase_09 AC 229 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,bmi2,lzcnt,tune=native")
//#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC target ("sse4")
#pragma GCC optimize("O3")
//#pragma GCC optimize ("tree-vectorize")
//#pragma GCC optimize("unroll-loops")
#ifndef NDEBUG
#define NDEBUG
#endif
#include <cassert>
#include <ctime>
#include <cstdio>
#include <cstdbool>
#include <cstdint>
#include <initializer_list>
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;
using f64 = double;
u64 modmul(u64 a, u64 b, u64 n) noexcept { return (u64)(((u128)a) * ((u128)b) % ((u128)n)); }
u64 modpow(u64 a, u64 b, u64 n) noexcept {
    u64 t = ((b & 1) == 0) ? 1 : a;
    for (b >>= 1; b != 0; b >>= 1) { a = modmul(a, a, n); if ((b & 1) == 1) { t = modmul(t, a, n); } }
    return t;
}
bool miller_rabin(u64 n) noexcept {
    if (n == 2) { return true; }
    if (n < 2 || (n & 1) == 0) { return false; }
    u64 n1 = n - 1, d = n - 1;
    u32 s = 0;
    for (; (d & 1) == 0; d >>= 1) { s += 1; }
    for (const u64 base : {2,325,9375,28178,450775,9780504,1795265022}) {
        u64 a = base;
        if (a >= n) { a %= n; if (a == 0) { continue; } }
        u64 t = modpow(a, d, n);
        if (t == 1) { continue; }
        for (u32 j = 1; t != n1; ++j) {
            if (j >= s) { return false; }
            t = modmul(t, t, n);
        }
    }
    return true;
}
int main(int, char**) {
    struct timespec time_monotonic_start, time_process_start, time_monotonic_end, time_process_end;
    clock_gettime(CLOCK_MONOTONIC, &time_monotonic_start);
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &time_process_start);
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        unsigned long long x;
        scanf("%llu", &x);
        printf("%llu %d\n", x, miller_rabin((u64)x) ? 1 : 0);
    }
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &time_process_end);
    clock_gettime(CLOCK_MONOTONIC, &time_monotonic_end);
    f64 d_sec_monotonic =
        (f64)(time_monotonic_end.tv_sec - time_monotonic_start.tv_sec) +
        (f64)(time_monotonic_end.tv_nsec - time_monotonic_start.tv_nsec) / (1000 * 1000 * 1000);
    f64 d_sec_process =
        (f64)(time_process_end.tv_sec - time_process_start.tv_sec) +
        (f64)(time_process_end.tv_nsec - time_process_start.tv_nsec) / (1000 * 1000 * 1000);
    fprintf(stderr, "time_monotonic:%f, time_process:%f\n", d_sec_monotonic, d_sec_process);
}
0