結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー 👑 Mizar
提出日時 2022-08-29 02:29:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 227 ms / 9,973 ms
コード長 1,707 bytes
コンパイル時間 314 ms
コンパイル使用メモリ 30,208 KB
最終ジャッジ日時 2025-02-06 23:25:02
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main(int, char**)’:
main.cpp:36:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   36 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
main.cpp:39:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   39 |         scanf("%llu", &x);
      |         ~~~~~^~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <cstdio>
#include <ctime>
#include <cstdbool>
#include <cstdint>
uint64_t modmul(uint64_t a, uint64_t b, uint64_t n) { return (uint64_t)(((__uint128_t)a) * ((__uint128_t)b) % ((__uint128_t)n)); }
uint64_t modpow(uint64_t a, uint64_t b, uint64_t n) {
    if (b == 0) { return 1; }
    for (; (b & 1) == 0; b >>= 1) { a = modmul(a, a, n); }
    uint64_t t = a;
    for (b >>= 1; b != 0; b >>= 1) { a = modmul(a, a, n); if ((b & 1) == 1) { t = modmul(t, a, n); } }
    return t;
}
const uint64_t bases[] = {2,325,9375,28178,450775,9780504,1795265022};
bool miller_rabin(uint64_t n) {
    if (n == 2) { return true; }
    if (n < 2 || (n & 1) == 0) { return false; }
    uint64_t n1 = n - 1, d = n - 1;
    uint32_t s = 0;
    for (; (d & 1) == 0; d >>= 1) { s += 1; }
    for (const auto& base : bases) {
        uint64_t a = base;
        if (a >= n) { a %= n; if (a == 0) { continue; } }
        uint64_t t = modpow(a, d, n);
        if (t == 1) { continue; }
        for (uint32_t j = 1; t != n1; ++j) {
            if (j >= s) { return false; }
            t = modmul(t, t, n);
        }
    }
    return true;
}
int main(int argc, char *argv[]) {
    struct timespec start_time, end_time;
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start_time);
    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((uint64_t)x) ? 1 : 0);
    }
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end_time);
    double d_sec =
        (double)(end_time.tv_sec - start_time.tv_sec) +
        (double)(end_time.tv_nsec - start_time.tv_nsec) / (1000 * 1000 * 1000);
    fprintf(stderr, "time:%f\n", d_sec);
}
0