結果

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

ソースコード

diff # 

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

struct MillerRabin {
    using lint = long long;
private : 
    const lint val1 = 4759123141;
    const lint val2 = 341550071728321;
    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 mul (lint a, lint b, lint m) {
        return __int128_t(a) * b % m;
    }

    inline lint modpow(lint x, lint k, lint m){
        x %= m;
        lint a = 1, p = x;
        while(k > 0) {
            if (k % 2 == 0) { p = mul(p, p, m); k /= 2; }
            else { a = mul(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 < val1) {
            for (const lint &a : v1) {
                if (n < a) break;
                if (a == n) return true;
                if (modpow(a, d, n) == 1) continue;
                if (sub(a, n, d, s)) return false;
            }
        } else if (n < val2) {
            for (const lint &a : v2) {
                if (a == n) return true;
                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 (modpow(a, d, n) == 1) continue;
                if (sub(a, n, d, s)) return false;
            }
        }
        return true;
    }

};


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