結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー nonamaenonamae
提出日時 2022-08-22 20:47:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,345 bytes
コンパイル時間 3,234 ms
コンパイル使用メモリ 296,664 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-18 13:30:34
合計ジャッジ時間 3,470 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
#include <immintrin.h>

using i8 = std::int8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;
using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using u128 = __uint128_t;

template<typename T>
using vec = std::vector<T>;
template<typename T>
using vvec = std::vector<std::vector<T>>;
template<typename T>
using vvvec = std::vector<std::vector<std::vector<T>>>;

template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

template<typename T, typename U>
struct BarrettReduction {
    T m;
    T im;

    BarrettReduction() = default;
    explicit BarrettReduction(T m_) : m(m_), im((~T(0)) / m_) {}

    T get_mod() { return m; }
    std::pair<T, T> div_rem(T a) {
        if (m == 1) return { a, 0 };
        const T inv = im;
        T q = T((U(a) * U(inv)) >> __builtin_popcountll(T(~0)));
        T r = a - q * m;
        if (m <= r) {
            r -= m;
            q++;
        }
        return { q, r };
    }
    T div(T a) {
        return div_rem(a).first;
    }
    T rem(T a) {
        return div_rem(a).second;
    }
    T pow(T a, T k) {
        T ret = T(1);
        T mul = a;
        while (k > 0) {
            if (k & 1) ret = rem(ret * mul); 
            mul = rem(mul * mul);
            k >>= 1;
        }
        return ret;
    }
};


bool miller_rabin(u64 n) {
    {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (!(n & 1)) return false;
    }
    BarrettReduction<u64, u128> br(n);
    u64 m = n - 1;
    u64 d = m >> __builtin_ctzll(m);
    u64 base[] = { 2ul, 325ul, 9375ul, 28178ul, 450775ul, 9780504ul, 1795265022ul };
    for (int i = 0; i < 7; ++i) {
        if (n <= base[i]) break;
        u64 t = d;
        u64 y = u64(br.pow(base[i], t));
        while (t != m && y != 1 && y != m) {
            y = u64(br.rem(u128(y) * y));
            t <<= 1;
        }
        if (y != m && (!(t & 1))) return false;
    }
    return true;
}

int main() {
    u64 Q; std::cin >> Q;
    while (Q--) {
        u64 x; std::cin >> x;
        std::cout << x << " ";
        std::cout << (miller_rabin(x) ? "1\n" : "0\n");
    }
}
0