結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー logx
提出日時 2020-12-26 11:11:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 452 ms / 9,973 ms
コード長 2,425 bytes
コンパイル時間 1,811 ms
コンパイル使用メモリ 192,652 KB
最終ジャッジ日時 2025-01-17 07:28:32
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
constexpr long long big=int(1e9)+7;
constexpr long long INF=(long long)1e18;
const char newl='\n';

template<typename T,typename U>
T expm(T x,U y,long long mod=big){
    if(y==0)return 1;//0^0=1
    if(x==1||x==0)return x;
    if(y%2==1)return (expm(x,y-1,mod)*x)%mod;
    T t=expm(x,y/2,mod);
    return (t*t)%mod;
}


constexpr long long primetest[]={2,3,61};
constexpr long long primetest_big[]={2,3,5,7,11,13,17,19,23,29,31,37};
//O(N^(1/4))
//N>2^32では__int128_tが使える環境に限る
bool isprime(const long long x){
    if(x==0 || x==1)return false;
    const long long d=(x-1)/((x-1)&-(x-1));
    if(x<(1LL<<32)){
        if(x==2 || x==3 || x==61)return true;
        for(long long e:primetest){
            long long t=d;
            long long y=expm(e,t,x);
            if(y==1)continue;//とりあえずテスト通過.
            while(y!=x-1){//y=-1になったらその時点でテスト通過.
                y=(y*y)%x;//y=e^2t modx.
                if(y==1 || t==x-1)return false;//y==1:1の平方根に1,-1以外が存在.t==x-1:e^t!=1.
                t<<=1;
            }
        }
        return true;
    }
    else{
        for(__int128_t e:primetest_big){
            long long t=d;
            __int128_t y=expm(e,t,x);
            if(y==1)continue;//とりあえずテスト通過.
            while(y!=x-1){//y=-1になったらその時点でテスト通過.
                y=(y*y)%x;//y=e^2t modx.
                if(y==1 || t==x-1)return false;//y==1:1の平方根に1,-1以外が存在.t==x-1:e^t!=1.
                t<<=1;
            }
        }
        return true;
    }
}

bool simple_isprime(const long long x){
    if(x==0 || x==1)return false;
    if(x==2)return true;
    if(!(x&1))return false;
    for(long long i=3;i*i<=x;i+=2){
        if(x%i==0)return false;
    }
    return true;
}

long long findFactor(const long long n){
    //
    return 0;
}

int main(){
    /*int64_t seed = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count();mt19937_64 rnd(seed);
    uniform_int_distribution<long long> dist_N(INF*8,INF*9);
    int n=1e3;
    
    while(n--){
        long long x=dist_N(rnd);
        if(simple_isprime(x)!=isprime(x))cout << x << '\n';
    }*/
    int n;cin >> n;
    while(n--){
        long long x;cin >> x;
        cout << x << ' ' << isprime(x) << newl;
    }
}
0