結果
| 問題 |
No.8030 ミラー・ラビン素数判定法のテスト
|
| ユーザー |
 MtSaka
|
| 提出日時 | 2022-12-23 18:48:47 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 59 ms / 9,973 ms |
| コード長 | 16,252 bytes |
| コンパイル時間 | 1,956 ms |
| コンパイル使用メモリ | 198,764 KB |
| 最終ジャッジ日時 | 2025-02-09 19:11:32 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 10 |
ソースコード
#line 1 "code.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/3030"
#line 2 "library/template/template.hpp"
#include<bits/stdc++.h>
#line 3 "library/template/macro.hpp"
#define SELECT4(a,b,c,d,e,...) e
#define SELECT3(a,b,c,d,...) d
#define REP1(a) for(ll i=0;i<(ll)(a);++i)
#define REP2(i,a) for(ll i=0;i<(ll)(a);++i)
#define REP3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define REP4(i,a,b,c) for(ll i=(ll)(a);i<(ll)(b);i+=(ll)(c))
#define rep(...) SELECT4(__VA_ARGS__,REP4,REP3,REP2,REP1)(__VA_ARGS__)
#define RREP1(a) for(ll i=(ll)(a)-1;i>=0;--i)
#define RREP2(i,a) for(ll i=(ll)(a)-1;i>=0;--i)
#define RREP3(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);--i)
#define rrep(...) SELECT3(__VA_ARGS__,RREP3,RREP2,RREP1)(__VA_ARGS__)
#define all(v) std::begin(v),std::end(v)
#define rall(v) std::rbegin(v),std::rend(v)
#define INT(...) int __VA_ARGS__;scan(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;scan(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;scan(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;scan(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#line 3 "library/template/alias.hpp"
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pi=std::pair<int,int>;
using pl=std::pair<ll,ll>;
using vi=std::vector<int>;
using vl=std::vector<ll>;
using vs=std::vector<std::string>;
using vc=std::vector<char>;
using vvl=std::vector<vl>;
using vd=std::vector<double>;
using vp=std::vector<pl>;
using vb=std::vector<bool>;
template<typename T>
struct infinity{
static constexpr T MAX=std::numeric_limits<T>::max();
static constexpr T MIN=std::numeric_limits<T>::min();
static constexpr T value=std::numeric_limits<T>::max()/2;
static constexpr T mvalue=std::numeric_limits<T>::min()/2;
};
template<typename T>constexpr T INF=infinity<T>::value;
constexpr ll inf=INF<ll>;
constexpr ld EPS=1e-8;
constexpr ld PI=3.1415926535897932384626;
constexpr int dx[8]={1,0,-1,0,1,-1,-1,1};
constexpr int dy[8]={0,1,0,-1,1,1,-1,-1};
#line 5 "library/template/func.hpp"
inline constexpr int msb(ull x){
int res=x?0:-1;
if(x&0xffffffff00000000)x&=0xffffffff00000000,res+=32;
if(x&0xffff0000ffff0000)x&=0xffff0000ffff0000,res+=16;
if(x&0xff00ff00ff00ff00)x&=0xff00ff00ff00ff00,res+=8;
if(x&0xf0f0f0f0f0f0f0f0)x&=0xf0f0f0f0f0f0f0f0,res+=4;
if(x&0xcccccccccccccccc)x&=0xcccccccccccccccc,res+=2;
return res+(x&0xaaaaaaaaaaaaaaaa?1:0);
}
inline constexpr int ceil_log2(ull x){return x?msb(x-1)+1:0;}
inline constexpr int popcnt(ull x){
#if __cplusplus>=202002L
return std::popcount(x);
#endif
x=(x&0x5555555555555555)+((x>>1)&0x5555555555555555);
x=(x&0x3333333333333333)+((x>>2)&0x3333333333333333);
x=(x&0x0f0f0f0f0f0f0f0f)+((x>>4)&0x0f0f0f0f0f0f0f0f);
x=(x&0x00ff00ff00ff00ff)+((x>>8)&0x00ff00ff00ff00ff);
x=(x&0x0000ffff0000ffff)+((x>>16)&0x0000ffff0000ffff);
return (x&0x00000000ffffffff)+((x>>32)&0x00000000ffffffff);
}
template<typename T,typename U>
inline constexpr bool chmin(T&a,U b){return a>b&&(a=b,true);}
template<typename T,typename U>
inline constexpr bool chmax(T&a,U b){return a<b&&(a=b,true);}
inline constexpr ll gcd(ll a,ll b){
if(a<0)a=-a;
if(b<0)b=-b;
while(b){
std::swap(a%=b,b);
}
return a;
}
inline constexpr ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline constexpr bool is_prime(ll n){
if(n<=1)return false;
for(ll i=2;i*i<=n;i++){
if(n%i==0)return false;
}
return true;
}
inline constexpr ll my_pow(ll a,ll b){
ll res=1;
while(b){
if(b&1)res*=a;
a*=a;
b>>=1;
}
return res;
}
inline constexpr ll mod_pow(ll a,ll b,const ll&mod){
if(mod==1)return 0;
a%=mod;
ll res=1;
while(b){
if(b&1)(res*=a)%=mod;
(a*=a)%=mod;
b>>=1;
}
return res;
}
inline ll mod_inv(ll a,const ll&mod){
ll b=mod,x=1,u=0,t;
while(b){
t=a/b;
std::swap(a-=t*b,b);
std::swap(x-=t*u,u);
}
if(x<0)x+=mod;
return x;
}
template<typename T,typename U>
std::ostream &operator<<(std::ostream&os,const std::pair<T,U>&p){os<<p.first<<" "<<p.second;return os;}
template<typename T,typename U>
std::istream &operator>>(std::istream&is,std::pair<T,U>&p){is>>p.first>>p.second;return is;}
template<typename T>
std::ostream &operator<<(std::ostream&os,const std::vector<T>&v){for(auto it=std::begin(v);it!=std::end(v);){os<<*it<<((++it)!=std::end(v)?" ":"");}return os;}
template<typename T>
std::istream &operator>>(std::istream&is,std::vector<T>&v){for(T &in:v){is>>in;}return is;}
inline void scan(){}
template<class Head,class... Tail>
inline void scan(Head&head,Tail&... tail){std::cin>>head;scan(tail...);}
template<class T>
inline void print(const T &t){std::cout<<t<<'\n';}
template<class Head, class... Tail>
inline void print(const Head &head, const Tail &... tail){std::cout<<head<<' ';print(tail...);}
template<class... T>
inline void fin(const T &... a){print(a...);exit(0);}
#line 5 "library/template/util.hpp"
struct IOSetup{
IOSetup(){
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
std::cout.tie(0);
std::cout<<std::fixed<<std::setprecision(12);
std::cerr<<std::fixed<<std::setprecision(12);
}
};
template<typename F>
struct REC{
private:
F f;
public:
explicit constexpr REC(F&&f_):f(std::forward<F>(f_)){}
template<typename... Args>
constexpr auto operator()(Args&&...args)const{
return f(*this, std::forward<Args>(args)...);
}
};
template<typename T,typename Comp=std::less<T>>
struct compressor{
private:
std::vector<T>data;
Comp cmp;
bool sorted=false;
public:
compressor():compressor(Comp()){}
compressor(const Comp&cmp):cmp(cmp){}
compressor(const std::vector<T>&dat,const Comp&cmp=Comp()):data(dat),cmp(cmp){}
compressor(std::vector<T>&&dat,const Comp&cmp=Comp()):data(move(dat)),cmp(cmp){}
compressor(std::initializer_list<T>li,const Comp&cmp=Comp()):data(li.begin(),li.end()),cmp(cmp){}
void push_back(const T&v){assert(!sorted);data.push_back(v);}
void push_back(T&&v){assert(!sorted);data.push_back(move(v));}
template<typename... Args>void emplace_back(Args&&...args){assert(!sorted);data.emplace_back(std::forward<Args>(args)...);}
void push(const std::vector<T>&v){
assert(!sorted);
const int n=data.size();
data.resize(v.size()+n);
for(int i=0;i<(int)v.size();i++)data[i+n]=v[i];
}
void build(){
assert(!sorted);sorted=1;
std::sort(data.begin(),data.end(),cmp);
data.erase(unique(data.begin(),data.end(),[&](const T&l,const T&r)->bool {return !cmp(l,r)&&!cmp(r,l);}),data.end());
}
const T&operator[](int k)const& {
assert(sorted);
return data[k];
}
int get_index(const T&v)const {
assert(sorted);
return int(lower_bound(data.begin(),data.end(),v,cmp)-data.begin());
}
void press(std::vector<T>&v)const {
assert(sorted);
for(auto&&i:v)i=get_index(i);
}
std::vector<int>pressed(const std::vector<T>&v)const {
assert(sorted);
std::vector<int>ret(v.size());
for(int i=0;i<(int)v.size();i++)ret[i]=get_index(v[i]);
return ret;
}
int size()const {
assert(sorted);
return data.size();
}
};
#line 4 "library/template/debug.hpp"
template<typename T,typename=void>
struct is_specialize:std::false_type{};
template<typename T>
struct is_specialize<T,typename std::conditional<false,typename T::iterator, void>::type>:std::true_type{};
template<typename T>
struct is_specialize<T,typename std::conditional<false,decltype(T::first),void>::type>:std::true_type{};
template<typename T>
struct is_specialize<T,std::enable_if_t<std::is_integral<T>::value,void>>:std::true_type{};
inline void dump(const char&t){std::cerr<<t;}
inline void dump(const std::string&t){std::cerr<<t;}
inline void dump(const bool&t){std::cerr<<(t?"true":"false");}
template <typename T,std::enable_if_t<!is_specialize<T>::value,std::nullptr_t> =nullptr>
inline void dump(const T&t){std::cerr<<t;}
template<typename T>
inline void dump(const T&t,std::enable_if_t<std::is_integral<T>::value>* =nullptr){std::string tmp;if(t==infinity<T>::value||t==infinity<T>::MAX)tmp="inf";if(std::is_signed<T>::value&&(t==infinity<T>::mvalue||t==infinity<T>::MIN))tmp="-inf";if(tmp.empty())tmp=std::to_string(t);std::cerr<<tmp;}
template<typename T,typename U>
inline void dump(const std::pair<T,U>&);
template<typename T>
inline void dump(const T&t,std::enable_if_t<!std::is_void<typename T::iterator>::value>* =nullptr){std::cerr<<"{";for(auto it=std::begin(t);it!=std::end(t);){dump(*it);std::cerr<<(++it==t.end()?"":",");}std::cerr<<"}";}
template<typename T,typename U>
inline void dump(const std::pair<T,U>&t){std::cerr<<"(";dump(t.first);std::cerr<<",";dump(t.second);std::cerr<<")";}
inline void trace(){std::cerr<<std::endl;}
template<typename Head,typename... Tail>
inline void trace(Head&&head,Tail&&... tail){dump(head);if(sizeof...(tail))std::cerr<<",";trace(std::forward<Tail>(tail)...);}
#ifdef ONLINE_JUDGE
#define debug(...) (void(0))
#else
#define debug(...) do{std::cerr<<#__VA_ARGS__<<"=";trace(__VA_ARGS__);}while(0)
#endif
#line 4 "library/template/type-traits.hpp"
template<std::size_t size>
struct int_least{
static_assert(size<=128,"size must be less than or equal to 128");
using type=typename std::conditional<
size<=8,std::int_least8_t,
typename std::conditional<
size<=16,std::int_least16_t,
typename std::conditional<
size<=32,std::int_least32_t,
typename std::conditional<size<=64,std::int_least64_t,__int128_t>::type>::type>::type>::type;
};
template<std::size_t size>using int_least_t=typename int_least<size>::type;
template<std::size_t size>
struct uint_least{
static_assert(size<=128,"size must be less than or equal to 128");
using type=typename std::conditional<
size<=8,std::uint_least8_t,
typename std::conditional<
size<=16,std::uint_least16_t,
typename std::conditional<
size<=32,std::uint_least32_t,
typename std::conditional<size<=64,std::uint_least64_t,__uint128_t>::type>::type>::type>::type;
};
template<std::size_t size>using uint_least_t=typename uint_least<size>::type;
template<typename T>
using double_size_int=int_least<std::numeric_limits<T>::digits*2+1>;
template<typename T>using double_size_int_t=typename double_size_int<T>::type;
template<typename T>
using double_size_uint=uint_least<std::numeric_limits<T>::digits*2>;
template<typename T>using double_size_uint_t=typename double_size_uint<T>::type;
template<typename T>
using double_size=typename std::conditional<std::is_signed<T>::value,double_size_int<T>,double_size_uint<T>>::type;
template<typename T>using double_size_t=typename double_size<T>::type;
#line 9 "library/template/template.hpp"
using namespace std;
#line 3 "library/math/modular/montgomery-modint.hpp"
template<typename T>
struct MontgomeryReduction{
static_assert(is_integral<T>::value,"template argument must be integral");
static_assert(is_unsigned<T>::value,"template argument must be unsigned");
private:
using large_t=typename double_size_uint<T>::type;
static constexpr int lg=numeric_limits<T>::digits;
T mod;
T r;
T r2;
T minv;
T calc_inv()const{
T t=0,res=0;
rep(i,lg){
if(~t&1){
t+=mod;
res+=static_cast<T>(1)<<i;
}
t>>=1;
}
return res;
}
public:
MontgomeryReduction(T x){set_mod(x);}
static constexpr int get_lg(){return lg;}
void set_mod(T x){
assert(x>0);
assert(x&1);
assert(x<=INF<T>);
mod=x;
r=(-static_cast<T>(mod))%mod;
r2=(-static_cast<large_t>(mod))%mod;
minv=calc_inv();
}
inline T get_r()const{return r;}
inline T get_mod()const{return mod;}
T reduce(large_t x)const{
large_t tmp=(x+static_cast<large_t>(static_cast<T>(x)*minv)*mod)>>lg;
return tmp>=mod?tmp-mod:tmp;
}
T transform(large_t x)const{return reduce(x*r2);}
};
template<typename T,int id>
struct MontgomeryModInt{
static_assert(is_integral<T>::value,"template argument must be integral");
static_assert(is_unsigned<T>::value,"template argument must be unsigned");
private:
using large_t=typename double_size_uint<T>::type;
T val;
static MontgomeryReduction<T>reduction;
public:
MontgomeryModInt():val(0){}
template<typename U,typename enable_if<is_integral<U>::value&&is_unsigned<U>::value>::type* =nullptr>
MontgomeryModInt(U x):val(reduction.transform(x<(static_cast<large_t>(reduction.get_mod())<<reduction.get_lg())?static_cast<large_t>(x):static_cast<large_t>(x%reduction.get_mod()))){}
template<typename U,typename enable_if<is_integral<U>::value&&is_signed<U>::value>::type* =nullptr>
MontgomeryModInt(U x):MontgomeryModInt(static_cast<typename std::make_unsigned<U>::type>(x<0?-x:x)){
if(x<0&&val)val=reduction.get_mod()-val;
}
T get()const{return reduction.reduce(val);}
static T get_mod(){return reduction.get_mod();}
static void set_mod(T x){reduction.set_mod(x);}
MontgomeryModInt& operator++(){
val+=reduction.get_r();
if(val>=reduction.get_mod())val-=reduction.get_mod();
return *this;
}
MontgomeryModInt operator++(int){
MontgomeryModInt res=*this;
++*this;
return res;
}
MontgomeryModInt& operator--(){
if(val<reduction.get_r())val+=reduction.get_mod();
val-=reduction.get_r();
return *this;
}
MontgomeryModInt operator--(int){
MontgomeryModInt res=*this;
--*this;
return res;
}
MontgomeryModInt& operator+=(const MontgomeryModInt&r){
val+=r.val;
if(val>=reduction.get_mod())val-=reduction.get_mod();
return *this;
}
MontgomeryModInt& operator-=(const MontgomeryModInt&r){
if(val<r.val)val+=reduction.get_mod();
val-=r.val;
return *this;
}
MontgomeryModInt& operator*=(const MontgomeryModInt&r){
val=reduction.reduce(static_cast<large_t>(val)*r.val);
return *this;
}
MontgomeryModInt pow(ull n)const{
MontgomeryModInt res=1,tmp=*this;
while(n){
if(n&1)res*=tmp;
tmp*=tmp;
n>>=1;
}
return res;
}
MontgomeryModInt inv()const{return pow(reduction.get_mod()-2);}
MontgomeryModInt& operator/=(const MontgomeryModInt&r){return *this*=r.inv();}
friend MontgomeryModInt operator+(const MontgomeryModInt&l,const MontgomeryModInt&r){return MontgomeryModInt(l)+=r;}
friend MontgomeryModInt operator-(const MontgomeryModInt&l,const MontgomeryModInt&r){return MontgomeryModInt(l)-=r;}
friend MontgomeryModInt operator*(const MontgomeryModInt&l,const MontgomeryModInt&r){return MontgomeryModInt(l)*=r;}
friend MontgomeryModInt operator/(const MontgomeryModInt&l,const MontgomeryModInt&r){return MontgomeryModInt(l)/=r;}
friend bool operator==(const MontgomeryModInt&l,const MontgomeryModInt&r){return l.val==r.val;}
friend bool operator!=(const MontgomeryModInt&l,const MontgomeryModInt&r){return l.val!=r.val;}
friend ostream &operator<<(ostream &os,const MontgomeryModInt&x){
return os<<x.get();
}
friend istream &operator>>(istream &is,MontgomeryModInt&x){
ll tmp;
is>>tmp;
x=MontgomeryModInt(tmp);
return is;
}
};
template<typename T,int id>
MontgomeryReduction<T>
MontgomeryModInt<T,id>::reduction=MontgomeryReduction<T>(998244353);
using ArbitraryModInt=MontgomeryModInt<unsigned int,-1>;
/**
* @brief MontgomeryModInt(モンゴメリ乗算)
*/
#line 4 "library/math/number/miller-rabin.hpp"
template<typename T>
constexpr bool miller_rabin(ull n,const ull base[],int sz){
if(T::get_mod()!=n)T::set_mod(n);
ull d=n-1;
while(~d&1)d>>=1;
const T e1=1,e2=n-1;
rep(i,sz){
ull a=base[i];
if(n<=a)return true;
ull t=d;
T y=T(a).pow(t);
while(t!=n-1&&y!=e1&&y!=e2){
y*=y;
t<<=1;
}
if(y!=e2&&(~t&1))return false;
}
return true;
}
constexpr bool is_prime_fast(ull n){
constexpr ull base_int[3]={2,7,61},base_ll[7]={2,325,9375,28178,450775,9780504,1795265022};
if(n==2)return true;
if(n<2||n%2==0)return false;
if(n<(1u<<31))return miller_rabin<MontgomeryModInt<unsigned int,-2>>(n,base_int,3);
return miller_rabin<MontgomeryModInt<ull,-2>>(n,base_ll,7);
}
template<ull n>constexpr bool is_prime_v=is_prime_fast(n);
/**
* @brief Miller-Rabin Primality Test(ミラーラビン素数判定)
*/
#line 4 "code.cpp"
int main(){
INT(n);
while(n--){
LL(x);
print(x,is_prime_fast(x));
}
}