結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー tSijEG6OkepBhhptSijEG6OkepBhhp
提出日時 2022-12-30 21:22:29
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 1,037 bytes
コンパイル時間 2,829 ms
コンパイル使用メモリ 156,388 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-05-04 09:44:50
合計ジャッジ時間 4,705 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <math.h>
#include <cassert>
#include <bitset>
#include <map>
#include <algorithm>
#include <iterator>
#include <string>
#include <utility>
#include <numeric>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
using P=pair<ll,ll>;
#define reps(i,a,n) for(int i=a;i<n;i++)
#define rep(i,n) reps(i,0,n)
#define all(x) x.begin(),x.end()
vector<ll>a{2,325,9375,28178,450775,9780504,1795265022};
bool solve(ll n){
  if(n==1)return 0;
    ll d=n-1;
    int s=0;
    while(d%2==0){d/=2;s++;}
    rep(i,7){
        if(a[i]%n==0)continue;
        ll ad=pow_mod(a[i],d,n);
        if(ad==1||ad==n-1)continue;
        bool ok=true;
        rep(j,s+1){
            ad*=ad;
            ad%=n;
            if(ad==n-1)ok=false;
        }
        if(ok){
            return false;
        }
    }
    return true;
}
int main(){
  int n;
  cin>>n;
  rep(i,n){
    ll x;
    cin>>x;
    cout<<x<<' '<<solve(x)<<endl;
  }
}
0