結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー kya_ski
提出日時 2020-04-05 13:32:26
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,997 bytes
コンパイル時間 1,641 ms
コンパイル使用メモリ 166,932 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-18 17:48:43
合計ジャッジ時間 2,548 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

struct MillerRabin {
    using lint = unsigned long long int;
private : 
    const lint v1[3] = {2, 7, 61};
    const lint v2[7] = {2, 3, 5, 7, 11, 13, 17};
    const lint v3[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
public : 
    inline lint modpow(lint x, lint k, lint m){
        x %= m;
        lint a = 1, p = x;
        while(k > 0) {
            if (k % 2 == 0) { p = p * p % m; k /= 2; }
            else { a = a * p % m; k--; }
        }
        return a;
    }

    inline bool sub (lint a, lint n, lint d, lint s) {
        bool flag = true;
        for (lint r = 0; r < s; r++) {
            if (modpow(a, d, n) == n - 1) {
                flag = false; break;
            }
            d <<= 1LL;
        }
        return flag;
    }

    bool isprime (lint n) {
        if (n < 2) return false;
        lint d = n - 1, s = 0;
        while (d % 2 == 0) { d /= 2; s++; }
        if (n < 4759123141LL) {
            for (const lint &a : v1) {
                if (a == n) return true;
                if (n < a) break;
                if (modpow(a, d, n) == 1) continue;
                if (sub(a, n, d, s)) return false;
            }
        } else if (n < 341550071728321LL) {
            for (const lint &a : v2) {
                if (a == n) return true;
                if (n < a) break;
                if (modpow(a, d, n) == 1) continue;
                if (sub(a, n, d, s)) return false;
            }
        } else {
            for (const lint &a : v3) {
                if (a == n) return true;
                if (n < a) break;
                if (modpow(a, d, n) == 1) continue;
                if (sub(a, n, d, s)) return false;
            }
        }
        return true;
    }

};


int main() {
    MillerRabin miller;
    
    int q;
    cin >> q;
    
    long long n;
    while (q--) {
        long long n;
        cin >> n;
        cout << n << ' ' << miller.isprime(n) << '\n';
    }
    return 0;
}
0