結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー nonamae
提出日時 2022-08-22 20:42:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,018 bytes
コンパイル時間 4,351 ms
コンパイル使用メモリ 378,008 KB
最終ジャッジ日時 2025-01-31 02:57:03
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

// clang-format off
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("omit-frame-pointer")
// #pragma GCC optimize("inline")
// #pragma GCC option("arch=native")
// #pragma GCC option("no-zero-upper")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#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; }
//clang-format on

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;
    }
};

struct BarrettReduction128 {
    u128 m;
    u128 im;

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

    u128 get_mod() { return m; }
    std::pair<u128, u128> div_rem(u128 a) {
        if (m == 1) return { a, 0 };
        const u128 inv = im;
        const u128 mask = 0xffffffffffffffffull;
        u128 au = a >> 64;
        u128 ad = a & mask;
        u128 imu = inv >> 64;
        u128 imd = inv & mask;
        u128 q = au * imu;
        u128 x = (ad * imd) >> 64;
        u128 auximd = au * imd;
        u128 adximu = ad * imu;
        if (std::numeric_limits<u128>::max() - x >= auximd)
            q++;
        x += auximd;
        if (std::numeric_limits<u128>::max() - x >= adximu)
            q++;
        x += adximu;
        q += x >> 64;
        u128 r = a - q * m;
        if (m <= r) {
            r -= m;
            q++;
        }
        return { q, r };
    }
    u128 div(u128 a) {
        return div_rem(a).first;
    }
    u128 rem(u128 a) {
        return div_rem(a).second;
    }
    u128 pow(u128 a, u128 k) {
        u128 ret = 1;
        u128 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;
    }
    BarrettReduction128 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" : "0") << "\n";
    }
}
0