結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー syarosyaro
提出日時 2019-01-22 01:19:40
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 377 ms / 9,973 ms
コード長 9,068 bytes
コンパイル時間 1,276 ms
コンパイル使用メモリ 100,800 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-16 23:11:40
合計ジャッジ時間 3,002 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

/* <rab:include(prime.hpp)> */
/* <rab:include(base.hpp)> */
#pragma GCC optimize ("O3")
void solve(); /* この関数に問題ごとの処理を書く */

#if defined(EBUG) && !defined(ONLINE_JUDGE)
  #define debug true
#else
  #define NDEBUG /* <cassert>のincludeより前に定義する必要がある */
  #define debug false
#endif
#include<algorithm>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<vector>
#ifdef __cpp_lib_execution
  #include<execution>
#endif
#include<cassert>
#include<cstdio>
#include<cstdlib>

using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define int LL /* 標準ライブラリのincludeが終わってから書き換える */
#define times(n, i)      uptil(0, n, i)
#define rtimes(n, i)     downto((n) - 1, 0, i)
#define upto(f, t, i)    for(auto rab_base_dest = (t), i = decltype(t)(f); i <= rab_base_dest; i++)
#define uptil(f, t, i)   for(auto rab_base_dest = (t), i = decltype(t)(f); i <  rab_base_dest; i++)
#define downto(f, t, i)  for(auto rab_base_dest = decltype(f)(t), i = (f); i >= rab_base_dest; i--)
#define downtil(f, t, i) for(auto rab_base_dest = decltype(f)(t), i = (f); i >  rab_base_dest; i--)
#define iter(v) begin(v), end(v)
#define citer(v) cbegin(v), cend(v)
#if debug
  #define _GLIBCXX_DEBUG
  #define _LIBCPP_DEBUG 2
  #define _LIBCPP_DEBUG2 2
  #define ln << endl
#else
  #define ln << '\n'
#endif
#define tb << '\t'
#define sp << ' '
#ifdef __cpp_lib_execution
  #if debug
    #define PARABLE execution::par_unseq,
  #else
    #define PARABLE execution::seq,
  #endif
#else
  #define PARABLE /* none */
#endif
#define CS const
#define CX constexpr
#define IL inline
#define RT return
#define TL template
#define TN typename
#define lambda [&]
/* <rab:include(typedefs.hpp)> */
struct unit{};

using LD=long double;
TL<TN T>using vec=vector<T>;
TL<TN T>using vvec=vec<vec<T>>;
TL<TN T>using vvvec=vec<vvec<T>>;
TL<TN T>using vvvvec=vec<vvvec<T>>;

/* @rab:typedefs:dynamic */
using VI = vec<int>; using VB = vec<bool>; using HII = map<int,int>; 
/* </rab:include(typedefs.hpp)> */

#define foldl accumulate
#define scanl partial_sum
TL<TN T>IL bool amax(T&v,CS T&a){RT v<a&&(v=a,true);}
TL<TN T>IL bool amin(T&v,CS T&a){RT v>a&&(v=a,true);}

namespace kpl {
  template<class V, class W>
  static IL void append(V& v, const W& w) { copy(PARABLE citer(w), back_inserter(v)); }

  template<class V>
  static IL auto flatten(const V& xss, unsigned reserve_size = 0) -> vector<decltype(*begin(*begin(xss)))> {
    decltype(flatten(xss)) ret;
    ret.reserve(reserve_size);
    for(const auto& xs : xss) append(ret, xs);
    ret.shrink_to_fit();
    return move(ret);
  }

  template<class I>
  static inline bool is_in(I x, I l, I r) {
    return l <= x && x < r;
  }
}
/* <rab:include(util.hpp)> */
#ifndef __cpp_lib_exchange_function
  // #define __cpp_lib_exchange_function 201304L
  #define exchange exchange_RAB
  TL<class T, class U=T> T exchange(T& t, U&& u) {
    T ret = move(t); t = forward<U>(u); RT ret;
  }
#endif
#ifndef __cpp_lib_clamp
  // #define __cpp_lib_clamp 201603L
  #define clamp clamp_RAB
  TL<class T> CX CS T& clamp(CS T& a, CS T& mn, CS T& mx) {
    RT a < mn ? mn : a > mx ? mx : a;
  }
#endif
template<class V> void uniq_after_sort(V& v) { v.erase(unique(iter(v)), v.end()); }
template<class V> void sort_and_uniq(V& v) { sort(iter(v)); v.erase(unique(iter(v)), v.end()); }
/* </rab:include(util.hpp)> */
/* <rab:include(mod.hpp)> */
#ifdef MOD
  #if !defined(FORCE_MOD) && MOD != 1000000007 && MOD != 1000000009 && MOD != 998244353
    #error unknown mod MOD; if you really want to use (MOD) as mod, define FORCE_MOD.
  #endif
#else
  #define MOD 1000000007
#endif
/* <rab:include(power.hpp)> */
TL<class T> T power(T x,LL n){T rt(1);for(;n;n/=2){if(n%2)rt*=x;x*=x;}RT rt;}
int pow_mod(int x,int n,int m){int rt=1;for(;n;n/=2){if(n%2)rt=rt*x%m;x=x*x%m;}RT rt;}
int pow_mod_64(int y,int n,int m){__int128 rt=1,x=y;for(;n;n/=2){if(n%2)rt=rt*x%m;x=x*x%m;}RT rt;}
/* </rab:include(power.hpp)> */
IL CX int modulo(int a,int m){RT(a%=m,a>=0?a:a+m);}
TL<ULL mod=MOD>class MInt{
  /*
    int with modulo.
    // `mod` must be a prime for `log`.
    `mod` must be coprime to `val` for `inv` and to `m.val` for `operator/` and `operator/=`.
  */
  /*! https://ei1333.github.io/luzhiled/snippets/other/mod-int.html */
public:
  int val;
  CX MInt():val(0){}
  explicit CX MInt(int v):val(modulo(v,mod)){}
  MInt&operator+=(CS MInt&m){val+=m.val;if(val>=mod)val-=mod;RT*this;}
  MInt&operator-=(CS MInt&m){val-=m.val;if(val<0)val+=mod;RT*this;}
  MInt&operator*=(CS MInt&m){val=val*m.val%mod;RT*this;}
  MInt&operator/=(CS MInt&m){val=val*m.inv().val%mod;RT*this;}
  MInt operator+(CS MInt&m)CS{RT MInt(*this)+=m;}
  MInt operator-(CS MInt&m)CS{RT MInt(*this)-=m;}
  MInt operator*(CS MInt&m)CS{RT MInt(*this)*=m;}
  MInt operator/(CS MInt&m)CS{RT MInt(*this)/=m;}
  MInt operator-()CS{MInt m;m.val=val?mod-val:0;RT m;}
  bool operator==(CS MInt&m)CS{RT val==m.val;}
  bool operator!=(CS MInt&m)CS{RT val!=m.val;}
  //MInt pow(int n)CS{MInt x(*this),rt(1);while(n){if(n%2)rt*=x;x*=x;n/=2;}RT rt;}
  MInt pow(int n)CS{RT power(*this,n);}
  MInt inv()CS{int a=val,b=mod,x=1,y=0,t;while(b){t=a/b;swap(b,a-=t*b);swap(y,x-=t*y);}RT(MInt)x;}
  friend ostream&operator<<(ostream&o,CS MInt<mod>&m){RT o<<m.val;}
  friend istream&operator>>(istream&i,MInt<mod>&m){int v;i>>v;m=MInt<mod>(v);RT i;}
};
using mint=MInt<>;

constexpr mint operator"" _m(ULL n){RT mint(n);}
constexpr MInt<998244353>operator"" _m998244353(ULL n){RT MInt<998244353>(n);}
constexpr MInt<1000000007>operator"" _m1e9_7(ULL n){RT MInt<1000000007>(n);}
constexpr MInt<1000000009>operator"" _m1e9_9(ULL n){RT MInt<1000000009>(n);}

////#pragma rab:gsub \b(\d+)m\b mint(\1)
/* </rab:include(mod.hpp)> */
/* <rab:include(debug.hpp)> */
TL<class T>
IL istream&operator>>(istream&s,vec<T>&v){for(auto&&p:v)s>>p;RT s;}
TL<class T,class S>
IL ostream&operator<<(ostream&s,CS pair<T,S>&p){RT s<<"("<<p.first<<","<<p.second<<")";}
TL<class T>
IL ostream&operator<<(ostream&,CS vec<T>&);
TL<class T,class S>
IL ostream&operator<<(ostream&,CS map<T,S>&);
#define DEFINE_ITER_OUTPUT(s,x,sep){int i=0;for(CS auto&x##0_elem:x){if(i++)s<<sep;s<<x##0_elem;}RT s;}
TL<class T>
IL ostream&operator<<(ostream&s,CS vec<T>&v)DEFINE_ITER_OUTPUT(s,v,' ')
TL<class T,class S>
IL ostream&operator<<(ostream&s,CS map<T,S>&m)DEFINE_ITER_OUTPUT(s,m,' ')
TL<class T>
IL ostream&operator<<(ostream&s,CS vec<vec<T>>&w)DEFINE_ITER_OUTPUT(s,w,'\n')
TL<class T,class S>
IL ostream&operator<<(ostream&s,CS vec<map<T,S>>&v)DEFINE_ITER_OUTPUT(s,v,'\n')
/* </rab:include(debug.hpp)> */

signed main() {
  if(debug) cerr << "MOD: " << (MOD) ln;
  if(!debug) {
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
  cout << fixed << setprecision(20);
  cerr << fixed << setprecision(20);

  solve();

  return 0;
}
/* </rab:include(base.hpp)> */

/*
  N < 2**20: brute-force
    O(√N)
  otherwise: Miller-Rabin primality test
    O(12(logN)^2); 64bit以上で理論的にはO((logN)^4)
*/
/*!
  https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
  http://joisino.hatenablog.com/entry/2017/08/03/210000
  https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95
*/
VI rab_prime_mr_as = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
bool is_prime(int n) {
  assert(n >= 0);
  if(n <= 1) { return false; }
  /*if(n % 2 == 0) { return n == 2; }
  if(n % 3 == 0) { return n == 3; }
  if(n < (1<<28)) {
    for(int i = 5; i * i <= n; i += 6) {
      if(n % i == 0 || n % (i + 2) == 0) { return false; }
    }
    return true;
  } else*/ {
    int d = n - 1, s = 0;
    while(d % 2 == 0) { d /= 2; ++s; }
    for(int a : rab_prime_mr_as) {
      if(n == a) { return true; }
      __int128 f = pow_mod_64(a, d, n);
      if(f == 1) { continue; }
      times(s, r) {
        if(f == n - 1) { goto next_a; }
        f = f * f % n; /* f = pow_mod_64(a, d << r+1, n) */
      }
      return false;
      next_a:;
    }
    return true;
  }
}

/* O(NloglogN) */
VB are_primes(int n) {
  assert(n >= 0);
  VB ret(n + 1, true);
  ret[0] = false;
  if(n == 0) { return ret; }
  ret[1] = false;
  for(int i = 2; i * i < n; ++i) if(ret[i]) {
    for(int j = i * 2; j < n; j += i) { ret[j] = false; }
  }
  return ret;
}

/*-
  verification: ok
  https://atcoder.jp/contests/arc004/submissions/4016291
*/
HII prime_factor(int n) {
  HII ret;
  if(n <= 1) { return ret; }

  #define rab_prime_factor_loop_body(x) \
    while(n % (x) == 0) { ++ret[(x)]; n /= (x); }

  rab_prime_factor_loop_body(2);
  rab_prime_factor_loop_body(3);

  for(int i = 5; i * i <= n; i += 6) {
    rab_prime_factor_loop_body(i);
    rab_prime_factor_loop_body(i + 2);
  }
  if(n > 1) ++ret[n];
  return ret;
}
/* </rab:include(prime.hpp)> */

void solve() {
// NN(X)
/* <foxy.memo-area> */
int N;cin>>N;VI X(N);times(N,Ri_0){cin>>X[Ri_0];}
/* </foxy.memo-area> */

  times(N, i) cout << X[i] sp << (int)is_prime(X[i]) ln;
}

/* <rab:gen/> */
0