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

提出ソース
結果

問題	No.3030 ミラー・ラビン素数判定法のテスト
ユーザー	kusaf_
提出日時	2022-02-20 18:04:52
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	243 ms / 9,973 ms
コード長	16,879 bytes
コンパイル時間	5,253 ms
コンパイル使用メモリ	282,504 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-11-16 23:46:36
合計ジャッジ時間	6,283 ms
ジャッジサーバーID （参考情報）	judge1 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

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

raw source code
#include <bits/stdc++.h>
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define INI cin.tie(0);ios::sync_with_stdio(0);cout<<fixed<<setprecision(12);
#define overload2(a,b,c,...) c
#define overload3(a,b,c,d,...) d
#define overload4(a,b,c,d,e,...) e
#define overload5(a,b,c,d,e,f,...) f
#define overload6(a,b,c,d,e,f,g,...) g
//------------------------------------------------------------------------------
using ll = long long;
using db = long double;
using str = string;
using bl = bool;
//------------------------------------------------------------------------------
#define P pair
using pii = P<ll,ll>;
using pdd = P<db,db>;
//------------------------------------------------------------------------------
#define V vector
using vi = V<ll>;   using vvi = V<vi>; using vvvi = V<vvi>; using vvvvi = V<vvvi>;
using vd = V<db>;   using vvd = V<vd>;
using vc = V<char>; using vvc = V<vc>;
using vb = V<bl>;   using vvb = V<vb>;
using vs = V<str>;  using vvs = V<vs>;
using vp = V<pii>;  using vpd = V<pdd>;
#define vvi1(v,h,w)   vvi v(h,vi(w))
#define vvi2(v,h,w,n) vvi v(h,vi(w,n))
#define vvi(...) overload4(__VA_ARGS__,vvi2,vvi1)(__VA_ARGS__)
#define vvd1(v,h,w)   vvd v(h,vd(w))
#define vvd2(v,h,w,n) vvd v(h,vd(w,n))
#define vvd(...) overload4(__VA_ARGS__,vvd2,vvd1)(__VA_ARGS__)
#define vvc1(v,h,w)   vvc v(h,vc(w))
#define vvc2(v,h,w,n) vvc v(h,vc(w,n))
#define vvc(...) overload4(__VA_ARGS__,vvc2,vvc1)(__VA_ARGS__)
#define vvb1(v,h,w)   vvb v(h,vb(w))
#define vvb2(v,h,w,n) vvb v(h,vb(w,n))
#define vvb(...) overload4(__VA_ARGS__,vvb2,vvb1)(__VA_ARGS__)
#define vvvi1(v,x,y,z)   vvvi v(x,V<vi>(y,vi(z)))
#define vvvi2(v,x,y,z,n) vvvi v(x,V<vi>(y,vi(z,n)))
#define vvvi(...) overload5(__VA_ARGS__,vvvi2,vvvi1)(__VA_ARGS__)
#define vvvvi1(v,w,x,y,z)   vvvvi v(w,V<vvi>(x,V<vi>(y,vi(z))))
#define vvvvi2(v,w,x,y,z,n) vvvvi v(w,V<vvi>(x,V<vi>(y,vi(z,n))))
#define vvvvi(...) overload6(__VA_ARGS__,vvvvi2,vvvvi1)(__VA_ARGS__)
#define vv1(T,v,h,w)   V<V<T>> v(h,V<T>(w))
#define vv2(T,v,h,w,n) V<V<T>> v(h,V<T>(w,n))
#define vv(...) overload5(__VA_ARGS__,vv2,vv1)(__VA_ARGS__)
using graph = V<vi>;
template<typename T> using wgraph = V<V<P<ll,T>>>;
template<typename T,typename U> using umap = unordered_map<T,U>;
template<typename T> using que = queue<T>;
template<typename T> using deq = deque<T>;
template<typename T> using PQ = priority_queue<T,V<T>,greater<T>>; //昇順
template<typename T> using QP = priority_queue<T>; //降順
//------------------------------------------------------------------------------
#define fi first
#define sc second
#define MP make_pair
#define endl '\n'
#define en cout<<endl
#define SQ sqrt
#define si(v) ll(v.size())
#define PB(v,n) v.push_back(n)
#define PF(v,n) v.push_front(n)
#define PP(v) v.pop_back()
//------------------------------------------------------------------------------
#define lp1(n)        lp2(i,n)
#define lp2(i,n)      for(ll i=0;i<ll(n);i++)
#define lp3(i,n,m)    for(ll i=n;i<ll(m);i++)
#define lp4(i,n,m,c)  for(ll i=n;i<ll(m);i+=c)
#define lp(...)  overload4(__VA_ARGS__,lp4,lp3,lp2,lp1)(__VA_ARGS__)
#define lp1_(n)       lp(n+1)
#define lp2_(i,n)     lp(i,n+1)
#define lp3_(i,n,m)   lp(i,n,m+1)
#define lp4_(i,n,m,c) lp(i,n,m+1,c)
#define lp_(...) overload4(__VA_ARGS__,lp4_,lp3_,lp2_,lp1_)(__VA_ARGS__)
#define pl1(n)        pl2(i,n)
#define pl2(i,n)      for(ll i=n;i>=0;i--)
#define pl3(i,n,m)    for(ll i=n;i>=m;i--)
#define pl4(i,n,m,c)  for(ll i=n;i>=m:i-=c)
#define pl(...)  overload4(__VA_ARGS__,pl4,pl3,pl2,pl1)(__VA_ARGS__)
#define lpv1(v)       lp(si(v))
#define lpv2(i,v)     lp(i,si(v))
#define lpv3(i,n,v)   lp(i,n,si(v))
#define lpv(...) overload3(__VA_ARGS__,lpv3,lpv2,lpv1)(__VA_ARGS__)
#define comlp(i,j,n)  lp(i,n-1)lp(j,i+1,n)
#define lpa1(v)   lpa2(i,v)
#define lpa2(i,v) for(auto &i:v)
#define lpa(...) overload2(__VA_ARGS__,lpa2,lpa1)(__VA_ARGS__)
#define lpm1(m)   lpm2(i,m)
#define lpm2(i,m) for(auto i=m.begin();i!=m.end();i++)
#define lpm(...) overload2(__VA_ARGS__,lpm2,lpm1)(__VA_ARGS__)
//------------------------------------------------------------------------------
template<typename T,typename U> P<T,U> operator+(const P<T,U> &x,const P<T,U> &y) {return P<T,U>(x.fi+y.fi,x.sc+y.sc);}
template<typename T,typename U> P<T,U> operator-(const P<T,U> &x,const P<T,U> &y) {return P<T,U>(x.fi-y.fi,x.sc-y.sc);}
template<typename T,typename U> P<T,U> operator+=(P<T,U> &x,const P<T,U> &y){return x=x+y;}
template<typename T,typename U> P<T,U> operator-=(P<T,U> &x,const P<T,U> &y){return x=x-y;}
template<typename T,typename U> void operator++(P<T,U> &x) {x+=MP(T(1),U(1));}
template<typename T,typename U> void operator--(P<T,U> &x) {x-=MP(T(1),U(1));}
template<typename T,typename U> db operator%(const P<T,U> &x,const P<T,U> &y) {return SQ((x.fi-y.fi)*(x.fi-y.fi)+(x.sc-y.sc)*(x.sc-y.sc));}
template<typename T,typename U> istream&operator>>(istream &is,P<T,U> &x)       {return is>>x.fi>>x.sc;}
template<typename T,typename U> ostream&operator<<(ostream &os,const P<T,U> &x) {return os<<x.fi<<" "<<x.sc;}
template<typename T> istream&operator>>(istream &is,V<T> &v)         {lpm(v)is>>*i;return is;}
template<typename T> ostream&operator<<(ostream &os,const V<T> &v)   {lpm(v){if(i!=v.begin())os<<" ";os<<*i;}return os;}
template<typename T> ostream&operator<<(ostream &os,const V<V<T>> &v){lpv(v){if(i>0)en;lpm(j,v[i]){if(j!=v[i].begin())os<<" ";os<<*j;}}return os;}
template<typename T> void operator>>(V<T> &v,const T x){PB(v,x);}
template<typename T> void operator--(V<T> &v){PP(v);}
template<typename T> void operator>>(set<T> &s,const T x){s.insert(x);}
template<typename T> void operator<<(set<T> &s,const T x){s.erase(x);}
template<typename T> void operator>>(stack<T> &s,const T x){s.push(x);}
template<typename T> T operator--(stack<T> &s){T r=s.top();s.pop();return r;}
template<typename T> void operator>>(que<T> &q,const T x){q.push(x);}
template<typename T> T operator--(que<T> &q){T r=q.front();q.pop();return r;}
template<typename T> void operator>>(PQ<T> &q,const T x){q.push(x);}
template<typename T> T operator--(PQ<T> &q){T r=q.top();q.pop();return r;}
template<typename T> void operator>>(QP<T> &q,const T x){q.push(x);}
template<typename T> T operator--(QP<T> &q){T r=q.top();q.pop();return r;}
//------------------------------------------------------------------------------
template<typename... T>  void IN(T&... a) {(cin>>...>>a);}
template<typename T,typename... Ts> void PRINT(const T& a,const Ts&... b) {cout<<a;(cout<<...<<(cout<<' ',b));en;}
template<typename T,typename... Ts> void PRINT_(const T& a,const Ts&... b){cout<<a;(cout<<...<<(cout<<' ',b));}
template<typename T,typename... Ts> void COUT(const T& a,const Ts&... b)  {cout<<a;(cout<<...<<(en,b));en;}
template<typename T> void VOUT(V<T> &v) {lpv(v)COUT(v[i]);}
template<typename T,typename U> void VINI(V<T> &v,U n)       {lpv(v) v[i]=n;}
template<typename T,typename U> void VINI(V<V<T>> &v,U n)    {lpv(v)lpv(j,v[0]) v[i][j]=n;}
template<typename T,typename U> void VINI(V<V<V<T>>> &v,U n) {lpv(v)lpv(j,v[0])lpv(k,v[0][0]) v[i][j][k]=n;}
template<typename T,typename U> void VINI(V<V<T>> &v,ll x,ll y,U n)         {v.assign(x,V<T>(y,n));}
template<typename T,typename U> void VINI(V<T> &v,ll x,U n)                 {v.assign(x,n);}
template<typename T,typename U> void VINI(V<V<V<T>>> &v,ll x,ll y,ll z,U n) {v.assign(x,V<V<T>>(y,V<T>(z,n)));}
#define LL(...)   ll   __VA_ARGS__; IN(__VA_ARGS__)
#define DB(...)   db   __VA_ARGS__; IN(__VA_ARGS__)
#define STR(...)  str  __VA_ARGS__; IN(__VA_ARGS__)
#define CHAR(...) char __VA_ARGS__; IN(__VA_ARGS__)
#define PII(...)  pii  __VA_ARGS__; IN(__VA_ARGS__)
#define PDD(...)  pdd  __VA_ARGS__; IN(__VA_ARGS__)
#define VI(v,n) vi v(n); IN(v)
#define VD(v,n) vd v(n); IN(v)
#define VP(v,n) vp v(n); IN(v)
#define VVI(v,h,w) vvi(v,h,w); IN(v)
#define VVC(v,h,w) vvc(v,h,w); IN(v)
void GIN(graph &g,ll m)  {lp(m){LL(A,B);A--;B--;g[A]>>B;g[B]>>A;}}
void GIN_(graph &g,ll m) {lp(m){LL(A,B);A--;B--;g[A]>>B;}}
template<typename T> void GIN(wgraph<T> &g,ll m)  {lp(m){ll A,B;T C;IN(A,B,C);A--;B--;g[A]>>MP(B,C);g[B]>>MP(A,C);}}
template<typename T> void GIN_(wgraph<T> &g,ll m) {lp(m){ll A,B;T C;IN(A,B,C);A--;B--;g[A]>>MP(B,C);}}
#ifdef ONLINE_JUDGE
#define CHECK
#define DEBUG(...)
#define DEBUG_(q)
#else
#define CHECK COUT("------------------------------")
#define DEBUG(...) {PRINT_(#__VA_ARGS__); cout<<" : "; PRINT(__VA_ARGS__);}
#define DEBUG_(q) {cout<<#q<<" : ";auto q_=q;while(!q_.empty())cout<<--q_<<" ";en;}
#endif
//------------------------------------------------------------------------------
#define all1(v)     (v).begin(),(v).end()
#define all2(v,l)   (v).begin()+(l),(v).end()
#define all3(v,l,r) (v).begin()+(l),(v).begin()+(r)
#define all(...)    overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__)
#define lla(v)      (v).rbegin(),(v).rend()
#define SORT(...)    sort(all(__VA_ARGS__))
#define REVERSE(...) reverse(all(__VA_ARGS__))
#define RESORT(...)  SORT(__VA_ARGS__),REVERSE(__VA_ARGS__)
#define SUM(...)  accumulate(all(__VA_ARGS__),0LL)
#define SUMD(...) accumulate(all(__VA_ARGS__),db(0))
#define MAX(...) *max_element(all(__VA_ARGS__))
#define MIN(...) *min_element(all(__VA_ARGS__))
template<typename T,typename U> void AP(V<T> &v,U n) {lpv(v) v[i]+=n;}
template<typename T,typename U> void AP(V<P<T,T>> &v,U n,bl x=1,bl y=1){lpv(v){if(x)v[i].fi+=n;if(y)v[i].sc+=n;}}
template<typename T,typename U> void AP(V<V<T>> &v,U n) {lpv(v)lpv(j,v[0]) v[i][j]+=n;}
#define BS(v,x) binary_search(all(v),x)
template<typename T,typename U> ll LB(T &v,U x) {return lower_bound(all(v),x)-v.begin();} // a[i]<xとなるiの個数 / a[i]>=xとなる最初のi
template<typename T,typename U> ll UB(T &v,U x) {return upper_bound(all(v),x)-v.begin();} // a[i]<=xとなるiの個数 / a[i]>xとなる最初のi
template<typename T,typename U> ll CNT(T &v,U x){return count(all(v),x);}
template<typename T> void UNI(T &v) {SORT(v);v.erase(unique(all(v)),v.end());}
template<typename T> V<T> COMP(V<T> &v){V<T> r=v;UNI(r);lpv(v)v[i]=LB(r,v[i]);return r;}
template<typename T> V<T> COMP(V<T> &x,V<T> &y){V<T> v;lpv(x)v>>x[i],v>>x[i]+T(1),v>>y[i],v>>y[i]+T(1);UNI(v);lpv(x)x[i]=LB(v,x[i]),y[i]=LB(v,y[i]);return v;}
template<typename T> vi SCOMP(T &v){ll p=-1,n=si(v);vi r;lp(n-1)if(v[i]!=v[i+1]){PB(r,i-p);p=i;}PB(r,n-1-p);return r;}
template<typename T> V<T> ACSUM(V<T> &v){ll n=si(v);V<T> r(n+1);r[0]=0;lp(n)r[i+1]=r[i]+v[i];return r;}
template<typename T,typename U> V<T> VPFI(V<P<T,U>> &v){V<T> r(si(v));lpv(r)r[i]=v[i].fi;return r;}
template<typename T,typename U> V<U> VPSC(V<P<T,U>> &v){V<T> r(si(v));lpv(r)r[i]=v[i].sc;return r;}
#define NP(v) while(next_permutation(all(v)))
//------------------------------------------------------------------------------
const ll MOD=1000000007;
//const ll MOD=998244353;
const ll INF=(1LL<<60),FNI=-INF,MOOD=MOD*10,M1=100005,M2=200005;
const db EPS=1e-10,PI=acos(-1);
const ll DX[8]={0,0,1,-1,1,1,-1,-1},DY[8]={1,-1,0,0,1,-1,1,-1};
const ll TEN[19]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000};
const ll ONE[19]={1,11,111,1111,11111,111111,1111111,11111111,111111111,1111111111,11111111111,111111111111,1111111111111,11111111111111,111111111111111,1111111111111111,11111111111111111,111111111111111111,1111111111111111111};
const ll COMAX=2000010; // 変更
ll fac[COMAX],finv[COMAX],inv[COMAX];
bl COMflag=0;
template<typename T,typename... Ts> T min(T a,T b,T c,Ts... x) {return min(a,min(b,c,x...));}
template<typename T,typename... Ts> T max(T a,T b,T c,Ts... x) {return max(a,max(b,c,x...));}
template<typename T> T max(P<T,T> P) {return max(P.fi,P.sc);}
template<typename T> T min(P<T,T> P) {return min(P.fi,P.sc);}
template<typename T> T PA(P<T,T> P)  {return P.fi+P.sc;}
template<typename T> T PS(P<T,T> P)  {return P.fi-P.sc;}
ll GCD(ll x,ll y) {if(x<0)x=-x;if(y<0)y=-y;return __gcd(x,y);}
ll LCM(ll x,ll y) {return x/GCD(x,y)*y;}
template<typename T> void extGCD(ll a,ll b,T &x,T &y){if(b==0){x=1;y=0;return;}extGCD(b,a%b,y,x);y-=a/b*x;}
template<typename T,typename... Ts> T GCD(T a,T b,T c,Ts... x) {return GCD(a,GCD(b,c,x...));}
template<typename T,typename... Ts> T LCM(T a,T b,T c,Ts... x) {return LCM(a,LCM(b,c,x...));}
ll GCD(vi &v) {ll r=v[0];lpv(i,1,v)r=GCD(r,v[i]);return r;}
ll LCM(vi &v) {ll r=1;lpv(v)r=LCM(r,v[i]);return r;}
ll WA(ll n) {ll r=0;while(n!=0)r+=n%10,n/=10;return r;}
ll DIG(ll n) {ll r=0;while(n!=0)n/=10,r++;return r;}
void COMINI(ll m=MOD) {COMflag=1;fac[0]=fac[1]=finv[0]=finv[1]=inv[1]=1;lp(i,2,COMAX){fac[i]=fac[i-1]*i%m;inv[i]=m-inv[m%i]*(m/i)%m;finv[i]=finv[i-1]*inv[i]%m;}}
ll COM(ll n,ll k,ll m=MOD) {if(!COMflag)COMINI(m);if(n<0||k<0||n<k)return 0;return fac[n]*(finv[k]*finv[n-k]%m)%m;}
ll PER(ll n,ll k,ll m=MOD) {if(!COMflag)COMINI(m);if(n<0||k<0||n<k)return 0;return fac[n]*finv[n-k]%m;}
ll COM_(ll n,ll k,ll m=MOD) {if(!COMflag)COMINI(m);if(n<0||k<0||n<k)return 0;ll r=1;lp(k)(r*=n-i)%=MOD;return r*finv[k]%MOD;} // kが小さい場合
ll PER_(ll n,ll k,ll m=0) {ll r=1;lp(k){r*=n-i;if(m>0)r%=m;}return r;}
vvi COMTable(ll n,ll m=0) {vvi(r,n+1,n+1);lp_(n)lp_(j,i){if(j==0||j==i)r[i][j]=1;else r[i][j]=r[i-1][j-1]+r[i-1][j];if(m>0)r[i][j]%=m;}return r;} // nが小さい場合・m任意
ll nC2(ll n) {return n*(n-1)/2;}
ll MPOW(ll x,ll n,ll m=MOD) {x%=m;if(x==0)return 0;ll r=1;while(n>0){if(n&1)r=r*x%m;x=x*x%m;n>>=1;}return r;}
ll POW(ll x,ll n) {if(x==0)return 0;ll r=1;while(n>0){if(n&1)r=r*x;x=x*x;n>>=1;}return r;}
vi n_BASE(ll x,ll n,bl re=0) {vi r;while(x!=0){PB(r,x%n);(x-=(x%n))/=n;}if(re)REVERSE(r);return r;}
ll UP(ll a,ll b=2){return (a+b-1)/b;}
ll MA(ll a,ll b,ll m=MOD) {return (a+b)%m;}
ll MS(ll a,ll b,ll m=MOD) {return (a-b+m*10)%m;}
ll MM(ll a,ll b,ll m=MOD) {return a*b%m;}
ll MD(ll a,ll b,ll m=MOD) {ll c=m,x=1,y=0;while(c){ll t=b/c;b-=t*c;swap(b,c);x-=t*y;swap(x,y);}x%=m;if(x<0)x+=m;return (a%m)*x%m;}
ll FAC(ll n,ll m=MOD) {if(!COMflag)COMINI(m);return fac[n];}
vi PRIME_EX(ll n) {vi r;lp_(i,2,SQ(n)){if(n%i!=0)continue;ll e=0;while(n%i==0)e++,n/=i;PB(r,e);}if(n!=1)PB(r,1);return r;}
vi PRIME_P(ll n) {vi r;lp_(i,2,SQ(n)){if(n%i!=0)continue;while(n%i==0)n/=i;PB(r,i);}if(n!=1)PB(r,n);return r;}
vp PRIME(ll n) {vp r;lp_(i,2,SQ(n)){if(n%i!=0)continue;ll e=0;while(n%i==0)e++,n/=i;PB(r,MP(i,e));}if(n!=1)PB(r,MP(n,1));return r;}
umap<ll,ll> PRIMAP(ll n){umap<ll,ll> r;lp_(i,2,SQ(n))while(n%i==0)r[i]++,n/=i;if(n!=1)r[n]=1;return r;}
vi DIV(ll n) {vi r;lp_(i,1,SQ(n)){if(n%i==0){PB(r,i);if(i*i!=n)PB(r,n/i);}}SORT(r);return r;}
ll DIVCNT(ll n,ll d){ll r=0;while(n%d==0)n/=d,r++;return r;}
ll PSUM(vi &v,ll s,ll m=MOD){ll n=si(v);vvi(dp,n+3,s+3,0);dp[0][0]=1;lp(i,n)lp_(j,s){(dp[i+1][j]+=dp[i][j])%=m;if(j>=v[i])(dp[i+1][j]+=dp[i][j-v[i]])%=m;}return dp[n][s];}
ll LIS(vi &v) {vi dp(si(v),INF);lpv(v){auto p=lower_bound(all(dp),v[i]);*p=v[i];}return LB(dp,INF);}
vi Z_(str s) {vi r(si(s));for(ll i=1,j=0;i<si(s);i++){if(i+r[i-j]<j+r[j])r[i]=r[i-j];else{ll k=max(0LL,j+r[j]-i);while(i+k<si(s)&&s[k]==s[i+k])k++;r[i]=k;j=i;}}r[0]=si(s);return r;}
ll POPCNT(ll n){return __builtin_popcountll(n);}
bl isbin(ll n){return n&&(n&-n)==n;}
template<typename T,typename U> bl chmin(T&a,U b) {if(a>b){a=b;return 1;}return 0;}
template<typename T,typename U> bl chmax(T&a,U b) {if(a<b){a=b;return 1;}return 0;}
template<typename T,typename U> bl EQ(T a,U b) {return abs(a-b)<EPS;}
template<typename T> T POS(T x) {return max(T(0),x);}
template<typename S,typename T,typename U> bl BETWEEN(S a,T b,U c){return (a<=b&&b<=c)||(c<=b&&b<=a);}
#define Yes COUT("Yes")
#define No COUT("No")
#define YES COUT("YES")
#define NO COUT("NO")
#define YN1(x)     if(x){Yes;}else No
#define YN2(x,y)   if(x){COUT(y);return 0;}
#define YN3(x,y,n) if(x){COUT(y);}else COUT(n)
#define YN(...) overload3(__VA_ARGS__,YN3,YN2,YN1)(__VA_ARGS__)
#define IOUT(x) YN(x==INF,-1,x)
//==============================================================================

bool is_prime(ll x){
  using u128=__uint128_t;
  if(x==2||x==3||x==5||x==7)return 1;
  if(x%2==0||x%3==0||x%5==0||x%7==0)return 0;
  if(x<121) return x>1;
  ll d=(x-1)>>__builtin_ctzll(x-1);
  ll p=1,m=x-1;
  auto pow=[](ll x,ll n,ll mod){
    u128 r;
    x%=mod;
    if(n==0){r=1;return r;}
    r=1;
    u128 c=x;
    for(;n;n>>=1,c=(c*c)%mod) if(n&1) r=r*c%mod;
    return r;
  };
  auto ok=[&](ll a){
    auto y=pow(a,d,x);
    ll t=d;
    while(y!=p&&y!=m&&t!=x-1){
      y=y*y%x;
      t<<=1;
    }
    if(y!=m&&t%2==0)return 0;
    return 1;
  };
  if(x<(1ll<<32)) {for(ll a:{2,7,61}) if(!ok(a))return 0;}
  else{
    for(ll a:{2,325,9375,28178,450775,9780504,1795265022}){
      if(x<=a)return 1;
      if(!ok(a))return 0;
    }
  }
  return 1;
}

int main()
{ INI;
  LL(n);
  VI(a,n);
  lp(n)
  {
    cout<<a[i]<<" ";
    is_prime(a[i])?COUT(1):COUT(0);
  }
}
yukicoder

結果

テストケース

ソースコード
