#427063 (C++14) No.3030 ミラー・ラビン素数判定法のテスト

• 問題: No.3030 ミラー・ラビン素数判定法のテスト
• ユーザー: 👑 tute7627
• 提出日時: 2020-02-07 16:39:15
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: TLE
• 実行時間: -
• コード長: 9,625 bytes
• コンパイル時間: 2,306 ms
• コンパイル使用メモリ: 191,352 KB
• 実行使用メモリ: 10,276 KB
• 最終ジャッジ日時: 2024-11-18 17:48:24
• 合計ジャッジ時間: 68,855 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 8,448 KB
testcase_01	AC	2 ms; 8,448 KB
testcase_02	AC	6 ms; 8,448 KB
testcase_03	AC	17 ms; 8,448 KB
testcase_04	TLE	-
testcase_05	TLE	-
testcase_06	TLE	-
testcase_07	TLE	-
testcase_08	TLE	-
testcase_09	TLE	-

ソースコード

#include<bits/stdc++.h>
using namespace std;

//#define endl '\n'
#define lfs cout<<fixed<<setprecision(10)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (m) - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T>
void chmin(T &a,T b){if(a>b)a=b;}
template<typename T>
void chmax(T &a,T b){if(a<b)a=b;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
vector<ll>dx={1,0,-1,0,1,1,-1,-1};
vector<ll>dy={0,1,0,-1,1,-1,1,-1};
template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}
ostream &operator<<(ostream &os, pair<ll, ll>&p){
  return os << p.first << " " << p.second;
}  

class bigint {
private:
  static const int BASE = 100000000, LEN = 8;
  bool negative;
  std::vector<int> a;
  bigint& normalize();
public:
  bigint(long long x = 0);
  bigint(const std::string& s);
  bigint& operator = (const bigint& x);
  bigint& operator = (long long x);
  bigint& operator = (const std::string& s);
  const bool operator < (const bigint& x) const;
  const bool operator > (const bigint& x) const;
  const bool operator <= (const bigint& x) const;
  const bool operator >= (const bigint& x) const;
  const bool operator != (const bigint& x) const;
  const bool operator == (const bigint& x) const;
  bigint operator -() const;
  bigint& operator += (const bigint& x);
  bigint& operator -= (const bigint& x);
  bigint& operator *= (const bigint& x);
  bigint& operator /= (const bigint& x);
  bigint& operator %= (const bigint& x);
  const bigint operator + (const bigint& x) const;
  const bigint operator - (const bigint& x) const;
  const bigint operator * (const bigint& x) const;
  const bigint operator / (const bigint& x) const;
  const bigint operator % (const bigint& x) const;
  friend std::pair<bigint,bigint> divmod(const bigint& lhs, const bigint& rhs);
  friend std::istream& operator >> (std::ostream& is, bigint& x); //適当実装
  friend std::ostream& operator << (std::ostream& os, const bigint& x);
  friend const bigint abs(bigint x);
};
bigint& bigint::normalize() {
  int i = a.size()-1;
  while (i >= 0 && a[i] == 0) --i;
  a.resize(i+1);
  if (a.size() == 0) negative = false;
  return *this;
}
bigint::bigint(long long x) : negative(x<0) {
  x = abs(x);
  for (; x > 0; x /= BASE) a.push_back(x % BASE);
}
bigint::bigint(const std::string& s): negative(false) {
  int p = 0;
  if (s[p] == '-') { ++p; negative = true; }
  else if (s[p] == '+') { ++p; }
  for (int i = s.size()-1, v = BASE; i >= p; --i, v*=10) {
    int x = s[i]-'0';
    if (x < 0 || 9 < x) {
      std::cerr<<"error: parse error:"<<s<<std::endl;
      exit(1);
    } 
    if (v == BASE) {
      v = 1;
      a.push_back(x);
    } else a.back() += (x)*v;
  }
  normalize();
}
bigint& bigint::operator = (const bigint& x) {
  negative = x.negative;
  a = x.a;
  return *this;
}
bigint& bigint::operator = (long long x) { return *this = bigint(x); }
bigint& bigint::operator = (const std::string& s) { return *this = bigint(s); }
const bool bigint::operator < (const bigint& x) const {
  if (negative != x.negative) return negative < x.negative;
  if (a.size() != x.a.size()) return (a.size() < x.a.size())^negative;
  for(int i = a.size()-1; i >= 0; --i)
    if (a[i] != x.a[i]) return (a[i] < x.a[i])^negative;
  return false;
}
const bool bigint::operator > (const bigint& x) const { return x<(*this); }
const bool bigint::operator <= (const bigint& x) const { return !(x<(*this)); }
const bool bigint::operator >= (const bigint& x) const { return !((*this)<x); }
const bool bigint::operator != (const bigint& x) const { return (*this)<x || x<(*this); }
const bool bigint::operator == (const bigint& x) const { return !((*this)<x || x<(*this)); }
bigint bigint::operator -() const {
  bigint ret(*this);
  if (a.size()) ret.negative = !ret.negative;
  return ret;
}
bigint& bigint::operator += (const bigint& x) {
  if (negative != x.negative) return *this -= -x;
  if (a.size() < x.a.size()) a.resize(x.a.size());
  int tmp = 0;
  for (int i = 0; i < a.size(); ++i) {
    a[i] += (i<x.a.size()?x.a[i]:0) + tmp;
    tmp = a[i] / BASE;
    a[i] %= BASE;
  }
  if (tmp) a.push_back(1);
  return *this;
}
bigint& bigint::operator -= (const bigint& x) {
  if (negative != x.negative) return *this += -x;
  std::vector<int> b(x.a);
  if ((*this < x) ^ negative) {
    a.swap(b);
    negative = !negative;
  }
  for (int i = 0, tmp = 0; i < a.size(); ++i) {
    a[i] += BASE - (i<b.size()?b[i]:0) + tmp;
    tmp = a[i] / BASE - 1;
    a[i] %= BASE;
  }
  return this->normalize();
}
bigint& bigint::operator *= (const bigint& x) {
  negative ^= x.negative;
  std::vector<int> c(a.size()*x.a.size()+1);
  for (int i = 0; i < a.size(); ++i) {
    long long tmp = 0;
    for (int j = 0; j < x.a.size(); ++j) {
      long long v = (long long)a[i] * x.a[j] + c[i+j] + tmp;
      tmp = v / BASE;
      c[i+j] = (int)(v % BASE);
    }
    if (tmp) c[i+x.a.size()] += (int)tmp;
  }
  a.swap(c);
  return this->normalize();
}
bigint& bigint::operator /= (const bigint& x) {
  return *this = divmod(*this,x).first;
}
bigint& bigint::operator %= (const bigint& x) {
  return *this = divmod(*this,x).second;
}
const bigint bigint::operator + (const bigint& x) const {
  bigint res(*this); return res += x;
}
const bigint bigint::operator - (const bigint& x) const {
  bigint res(*this); return res -= x;
}
const bigint bigint::operator * (const bigint& x) const {
  bigint res(*this); return res *= x;
}
const bigint bigint::operator / (const bigint& x) const {
  bigint res(*this); return res /= x;
}
const bigint bigint::operator % (const bigint& x) const {
  bigint res(*this); return res %= x;
}
std::pair<bigint,bigint> divmod(const bigint& lhs, const bigint& rhs) {
  if (!rhs.a.size()) {
    std::cerr<<"error: division by zero"<<std::endl;
    exit(1);
  }
  bigint x(abs(rhs)), q, r;
  for (int i = lhs.a.size()-1; i >= 0; --i) {
    r = r * bigint::BASE + lhs.a[i];
    int head = 0, tail = bigint::BASE;
    if (r >= x) {
      while (head + 1 < tail) {
        int mid = (head + tail) / 2;
        if (x * bigint(mid) > r) tail = mid;
        else head = mid;
      }
      r -= x * head;
    }
    q.a.push_back(head);
  }
  reverse(q.a.begin(), q.a.end());
  bool neg = lhs.negative ^ lhs.negative;
  q.negative = neg; r.negative = neg;
  return std::make_pair(q.normalize(), r.normalize());
}
std::istream& operator >> (std::istream& is, bigint& x) {
  std::string tmp; is >> tmp;
  x = bigint(tmp);
  return is;
}
std::ostream& operator << (std::ostream& os, const bigint& x) {
  if (x.negative) os << '-';
  if (!x.a.size()) os << 0;
  else os << x.a.back();
  for (int i = x.a.size()-2; i >= 0; --i) {
    os.width(bigint::LEN);
    os.fill('0');
    os << x.a[i];
  }
  return os;
}
const bigint abs(bigint x) {
  x.negative = false;
  return x;
}
using ull = unsigned long long;
template<typename T>
struct FastPrime{
  T modpow(T p, ull q, ull mod){
    T tmp = p % mod, ret = 1;
    while(q){
      if(q&1)ret = ret * tmp % T(mod); 
      q >>= 1;
      tmp = tmp * tmp % T(mod);
    }
    return ret;
  }
  vector<T>v32={2,7,61};
  bool isPrime32(ull n){
    ull d = n - 1;
    while(!(d&1))d >>= 1;
    for(auto a:v32){
      if(T(n) <= a)break;
      T now = modpow(a, d, n);
      ull q = d;
      while(q != n - 1 && now != T(1) && now != T(n - 1)){
        q <<= 1;
        now = now * now % T(n);
      }
      if(!(q&1) && now != T(n-1))return false;
    }
    return true;
  }
  vector<T>v64={2,325,9375,28178,450775,9780504,1795265022};
  bool isPrime64(ull n){
    ull d = n - 1;
    while(!(d&1))d >>= 1;
    for(auto a:v64){
      if(T(n) <= a)break;
      T now = modpow(a, d, n);
      ull q = d;
      while(q != n - 1 && now != T(1) && now != T(n - 1)){
        q <<= 1;
        now = now * now % T(n);
      }
      if(!(q&1) && now != T(n-1))return false;
    }
    return true;
  }
  bool isPrime(ull n){
    if(n == 2)return true;
    else if(n == 1 || n % 2 == 0)return false;
    else if(n < 1UL << 31)return isPrime32(n);
    else return isPrime64(n);
  }
};
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  struct FastPrime<bigint> fp;
  ll n;cin>>n;
  rep(i,0,n){
    ll x;cin>>x;
    cout<<x spa fp.isPrime(x)<<endl;
  }
  return 0;
}