結果

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

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
//#include <atcoder/all>

using namespace std;
//using namespace atcoder;

#ifdef DEBUG
    #include "debug.h"
    #define dump(...)                                                              \
        DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
                << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
                << endl                                                            \
                << "    ",                                                         \
            dump_func(__VA_ARGS__)
#else
    #define dump(...)
#endif

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}

//#define int long long
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define YES puts("YES")
#define Yes puts("Yes")
#define NO  puts("NO")
#define No  puts("No")
#define ALL(v) (v).begin(), (v).end()
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
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 (a>b) { a=b; return 1; } return 0; }

//*
#define mod 1000000007 /*/
#define mod 998244353 //*/

typedef pair<int, int> P;
#define INF (1LL<<60)


bool isprime(int  n){
    if (n < 2) return false;
    if (n == 2) return true;
    for (int i = 2; i*i <= n; i++)
            if (n % i == 0) return false;

    return true;
}


using ll = long long;
// x^k mod m
long long modpow( ll x, ll k, ll m ){
    ll ret = 1;
    while(k > 0){
        if( ret % 2 == 1){
          ret = ((__uint128_t)ret * x) % m;
        }
        k /= 2;
        x = ((__uint128_t)x * x) % m;
    }
    return ret;
}

bool miller_rabin_primality_test(ll N){
    if(N<2) return false;
    if(N==2) return true;
    else if(N%2==0) return false;
    
    auto test = [&](int a){
        ll t = N-1, s=0;
        while(t % 2 == 0){
            t /= 2; s++;
        }
        ll r = modpow(a, t, N);
        if(r==1 || r==N-1) return true;
        for(int i=0; i<s; i++){
            r = ((__uint128_t)r * r) % N;
            if(r==N-1) return true;
        }
        return false;   // 合成数である
    };

    vector<int> witness;
    if(N < (1LL<<32))
        witness = {2, 7, 61};
    else
        witness = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    for(int a : witness){
        int g = gcd(a,N);
        if(1<g && g < N) return false;
        if(g==N) continue;
        if(!test(a)) return false;
    }
    return true;
}

void solve(){
    int N;
    cin >> N;
    while(N--){
        long long x;
        cin >> x;
        cout << x << " " << miller_rabin_primality_test(x) << endl;
    }
}


signed main(){
    cout << fixed << setprecision(18);
    cerr << fixed;
    solve();
}
0