#1044464 (C++23) No.8114 Prime Checker+1

提出ソース
結果

問題	No.8114 Prime Checker+1
ユーザー	clever-elsie
提出日時	2025-02-21 14:09:30
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	12,138 bytes
コンパイル時間	6,994 ms
コンパイル使用メモリ	352,156 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2025-02-21 14:09:38
合計ジャッジ時間	8,075 ms
ジャッジサーバーID （参考情報）	judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 30
権限があれば一括ダウンロードができます
ソースコード

raw source code
#ifndef ELSIE_LOCAL_H
#define ELSIE_LOCAL_H
#if __has_include(<atcoder/all>)
#include<atcoder/all>
using namespace atcoder;
using mint=modint998244353;
using mint1=modint1000000007;
#endif
#if __has_include(<ext/pb_ds/assoc_container.hpp>) && __has_include(<ext/pb_ds/tree_policy.hpp>)
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class s,class t>using __gnu_map=tree<s,t,std::less<s>,rb_tree_tag,tree_order_statistics_node_update>;
template<class s,class t>struct gnu_map:public __gnu_map<s,t>{
	using iterator=typename __gnu_map<s,t>::iterator;
	iterator get(int64_t idx){return this->find_by_order(idx<0?this->size()-idx:idx);}
	size_t ord(const s&key){return this->order_of_key(key);}
};
template<class s>struct gnu_set:public gnu_map<s,null_type>{gnu_map<s,null_type>::iterator operator[](int64_t i){return this->get(i);}};
#endif
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
using std::cin;
using std::cout;
using sstream=stringstream;
#define RET return
#define int long long
#define itn long long
#define fi first
#define se second
#define endl '\n'
#define sn(i,c) " \n"[i==c]
#define rsv(n) reserve(n)
#define pf(a) push_front(a)
#define pb(a) push_back(a)
#define eb(...) emplace_back(__VA_ARGS__)
#define ppf() pop_front()
#define ppb() pop_back()
#define pp() pop()
#define ins(a) insert(a)
#define emp(...) emplace(__VA_ARGS__)
#define ers(a) erase(a)
#define cont(a) contains(a)
#define mp(f,s) make_pair(f,s)
#define A(a) begin(a),end(a)
#define I(a,i) begin(a),begin(a)+(i)
#define elif(c) else if(c)
#define _SEL4(_1,_2,_3,_4,name,...) name
#define _SEL3(_1,_2,_3,name,...) name
#define _REP4(i,s,n,st) for(int i=(s);i<(n);i+=(st))
#define _REP3(i,s,n) _REP4(i,s,n,1)
#define _REP2(i,n) _REP3(i,0,n)
#define _REP1(n) _REP2(_,n)
#define _RREP4(i,n,t,s) for(int i=(n);i>=(t);i-=(s))
#define _RREP3(i,n,t) _RREP4(i,n,t,1)
#define _RREP2(i,n) _RREP3(i,n,0)
#define _ITER2(x,a) for(auto&x:a)
#define _ITER3(x,y,a) for(auto&[x,y]:a)
#define _CTER2(x,a) for(const auto&x:a)
#define _CTER3(x,y,a) for(const auto&[x,y]:a)
#define rep(...) _SEL4(__VA_ARGS__,_REP4,_REP3,_REP2,_REP1)(__VA_ARGS__)
#define rrep(...) _SEL4(__VA_ARGS__,_RREP4,_RREP3,_RREP2,_REP1)(__VA_ARGS__)
#define forif(c,...) rep(__VA_ARGS__)if(c)
#define iter(...) _SEL3(__VA_ARGS__,_ITER3,_ITER2)(__VA_ARGS__)
#define cter(...) _SEL3(__VA_ARGS__,_CTER3,_CTER2)(__VA_ARGS__)
#define _LB_BEX(b,e,x) lower_bound(b,e,x)
#define _LB_BEXG(b,e,x,g) lower_bound(b,e,x,g)
#define _UB_BEX(b,e,x) upper_bound(b,e,x)
#define _UB_BEXG(b,e,x,g) upper_bound(b,e,x,g)
#define lb(...) _SEL4(__VA_ARGS__,_LB_BEXG,_LB_BEX)(__VA_ARGS__)
#define ub(...) _SEL4(__VA_ARGS__,_UB_BEXG,_UB_BEX)(__VA_ARGS__)
#define rev(a) reverse(A(a))
#define minel(a) min_element(A(a))
#define maxel(a) max_element(A(a))
#define acm(a) accumulate(A(a),0ll)
#define nxpm(a) next_permutation(A(a))
#define Sort(a) sort(A(a))
#define uni(a) Sort(a);a.erase(unique(A(a)),a.end())
#define swapcase(a) a=(isalpha(a)?a^32:a)
#define NL cout<<'\n'
template<class f>using gr=greater<f>;
template<class f>using vc=vector<f>;
template<class f>using vv=vc<vc<f>>;
template<class f>using v3=vv<vc<f>>;
template<class f>using v4=vv<vv<f>>;
template<class f>using pq=priority_queue<f>;
template<class f>using pqg=priority_queue<f, vc<f>, gr<f>>;
#define uset unordered_set
#define umap unordered_map
using i8=int8_t; using i16=int16_t; using i32=int32_t; using i64=int64_t; using i128=__int128_t;
using u8=uint8_t;using u16=uint16_t;using u32=uint32_t;using u64=uint64_t;using u128=__uint128_t;
using intw=__int128_t;using uintw=__uint128_t; using it=i32;
using f32=float;using f64=double;using f128=__float128;
using vi=vc<int>;using vb=vc<bool>;
using pi=pair<int,int>;
using str=string;using vs=vc<str>;
using pqgp=pqg<pi>;
#define double f128
constexpr int inf=1ll<<60,minf=-inf;
constexpr char sep='\n';
constexpr array<pi,8>dc={{{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}}};
template<class T,class U>inline void chmax(T&a,const U&b){if(a<b)a=b;}
template<class T,class U>inline void chmin(T&a,const U&b){if(a>b)a=b;}
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define yn(c) (c)?yes:no
#if __cplusplus <= 202002L
#else
#define C const
namespace vies=std::views;
#define DR(i) views::drop(i)
#define TK(i) views::take(i)
#define RV views::reverse
#define IOTA vies::iota
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) str __VA_ARGS__;in(__VA_ARGS__)
#define VI(a,n) vi a(n);in(a)
#define VS(a,n) vs a(n);in(a)
#define UV(u,v) INT(u,v);--u,--v
#define UVW(u,v,w) INT(u,v,w);--u,--v
template<class T,class U>concept LUBI= same_as<T,vc<U>>||same_as<T,deque<U>>||is_array_v<T>;
#define TP template<class T,class U,typename cp=less<U>>
#define RL requires LUBI<T,U>
TP u64 lbi(C T&v,C U&x,cp cmp=cp())RL{RET lb(A(v),x,cmp)-begin(v);}
TP u64 ubi(C T&v,C U&x,cp cmp=cp())RL{RET ub(A(v),x,cmp)-begin(v);}
TP u64 lbi(u64 i,C T&v,C U&x,cp cmp=cp())RL{RET lb(i+A(v),x,cmp)-begin(v);}
TP u64 ubi(u64 i,C T&v,C U&x,cp cmp=cp())RL{RET ub(i+A(v),x,cmp)-begin(v);}
TP u64 lbi(C T&v,u64 i,C U&x,cp cmp=cp())RL{RET lb(I(v,i),x,cmp)-begin(v);}
TP u64 ubi(C T&v,u64 i,C U&x,cp cmp=cp())RL{RET ub(I(v,i),x,cmp)-begin(v);}
TP u64 lbi(u64 i,C T&v,u64 e,C U&x,cp cmp=cp())RL{RET lb(i+I(v,e),x,cmp)-begin(v);}
TP u64 ubi(u64 i,C T&v,u64 e,C U&x,cp cmp=cp())RL{RET ub(i+I(v,e),x,cmp)-begin(v);}
#undef TP
#undef RL
#define TP template
TP<class T>concept Lint=is_integral_v<T>&&sizeof(T)>8;
TP<Lint T>ostream&operator<<(ostream&dst,T val){
	ostream::sentry s(dst);
	if(!s)return dst;
	char _O128[64];
	char*d=end(_O128);
	bool vsign=val<0;
	uintw v=val;
	if(vsign&&val!=numeric_limits<T>::min())v=1+~(uintw)val;
	do{
		*(--d)="0123456789"[v%10];
		v/=10;
	}while(v!=0);
	if(vsign)*(--d)='-';
	size_t len=end(_O128)-d;
	if(dst.rdbuf()->sputn(d,len)!=len)dst.setstate(ios_base::badbit);
	return dst;
}
TP<Lint T>istream&operator>>(istream&src,T&val) {
	str s;src>>s;
	bool is_neg=numeric_limits<T>::is_signed&&s.size()>0&&s[0]=='-';
	for(val=0;C auto&x:s|views::drop(is_neg))val=10*val+x-'0';
	if(is_neg)val*=-1;
	return src;
}
istream&operator<<(istream&is,f128&x){f64 y;is>>y;x=y;return is;}
ostream&operator<<(ostream&os,const f128&x){return os<<static_cast<f64>(x);}
#define MUT make_unsigned_t
TP<integral T>i32 pcnt(T p){return popcount(MUT<T>(p));}
TP<integral T>i32 lsb(T p){return countl_zero(MUT<T>(p));}
TP<integral T>i32 msb(T p){return countr_zero(MUT<T>(p));}
TP<i32 N,integral T>void putbit(T s){
	char buf[N+1]={0};
	for(char*itr=buf+N-1;itr>=buf;itr--,s>>=1)
		*itr='0'+(s&1);
	cout<<buf<<sep;
}
TP<class T>concept Itrabl=requires(C T&x){x.begin();x.end();}&&!std::is_same_v<T,string>;
TP<class T>concept IItrabl=Itrabl<T>&&Itrabl<typename T::value_type>;
TP<class T>concept ModInt=requires(C T&x){x.val();};
TP<class T>concept NLobj=Itrabl<T>||std::is_same_v<T,string>;
TP<ModInt T>istream&operator>>(istream&is,T&v){int x;is>>x;v=x;return is;}
TP<class T,class U>istream&operator>>(istream&is,pair<T,U>&v){return is>>v.first>>v.second;}
TP<Itrabl T>istream&operator>>(istream&is,T&v){iter(x,v)is>>x;return is;}
TP<class T>void in(T&a){cin>>a;}
TP<class T,class... Ts>void in(T&a,Ts&... b){in(a);in(b...);}
TP<class T,class U>vc<pair<T,U>>zip(size_t n,size_t m){
	vc<pair<T,U>>r(min(n,m));
	iter(x,y,r)in(x);
	iter(x,y,r)in(y);
	return move(r);
}
TP<class T,class U>vc<pair<T,U>>zip(size_t n){return move(zip<T,U>(n,n));}
TP<ModInt T>ostream&operator<<(ostream&os,const T&v){return os<<v.val(); }
TP<Itrabl T>ostream&operator<<(ostream&os,const T&v){int cnt=0;cter(x,v)os<<x<<(++cnt<v.size()?" ":"");return os;}
TP<IItrabl T>ostream&operator<<(ostream&os,const T&v){int cnt=0;cter(x,v)os<<x<<(++cnt<v.size()?"\n":"");return os;}
TP<class T,class U>ostream&operator<<(ostream&os,const pair<T,U>&v){return os<<'('<<v.first<<','<<v.second<<')';}
ostream*dos=&cout;
int32_t OFLG; // 0:first, 1:notNLobj, 2:NLobj
TP<class T>void _out(const T&a){if(OFLG)(*dos)<<"0 \n"[OFLG]<<a;else(*dos)<<a;OFLG=1;}
TP<NLobj T>void _out(const T&a){(*dos)<<(OFLG?"\n":"")<<a;OFLG=2;}
TP<class T,class...Ts>void _out(const T&a,const Ts&... b){_out(a);_out(b...);}
TP<class... Ts>void out(const Ts&... v){OFLG=0;_out(v...);(*dos)<<sep;}
#undef TP
#undef C
#endif
#ifdef LOCAL
#define dput(...) dos=&cerr;out(__VA_ARGS__);dos=&cout
#else
#define dput(...)
#endif
#endif // include guard
#include <vector>
#include <limits>
#include <cstdint>
#include <concepts>
#include <atcoder/modint>
#ifndef ELSIE_BASIC_MATH
#define ELSIE_BASIC_MATH
namespace elsie{
	using namespace std;
	using namespace atcoder;

	template<integral T,integral U>
	inline auto ceil(const T a,const U b){return(a+b-1)/b;}
	template<integral T,integral U>
	inline auto floor(const T a,const U b){return a/b-(a%b&&(a^b)<0);}

	int64_t safepow(int64_t a,uint64_t b){
		int64_t ret=1,k=a;
		double check=1,kcheck=a;
		while(b){
			if(b&1){
				check*=k;
				if(check>INT64_MAX)return INT64_MAX;
				if(check<INT64_MIN)return INT64_MIN;
				ret*=k;
			}
			kcheck*=k;
			if(kcheck>INT64_MAX)return INT64_MAX;
			if(kcheck<INT64_MIN)return INT64_MIN;
			k*=k;
			b>>=1;
		}
		return ret;
	}

	int64_t modpow(int64_t a,uint64_t b,uint64_t mod){
		__uint128_t k=a%mod,ret=1;
		if(k<0)k+=mod;
		while(b){
			if(b&1)ret=(ret*k)%mod;
			k=(k*k)%mod;
			b>>=1;
		}
		return int64_t(ret);
	}

	template<class S>S gcd(S a,S b){
		if(b==0) return a;
		S r=1;if(a<0)a=-a;if(b<0)b=-b;
		while(r) r=a%b,a=b,b=r;
		return a;
	}

	template<class S>S lcm(S a,S b){return a/gcd(a,b)*b;}

	template<class S>S egcd(S a,S b,S&x,S&y){
		if(b==0){
			x=1,y=0;
			return a;
		}
		S d=egcd(b,a%b,y,x);
		y-=a/b*x;
		return d;
	}

	template<class T>T exgcd(T a,T b,T&x,T&y){
		auto assign=[&](T&s,T&t,T u,T v)->void {s=u,t=v;};
		x=1,y=0;
		T u=0,v=1;
		while(b){
			T k=a/b;
			T r=a%b;
			assign(a,b,b,r);
			assign(x,u,u,x-u*k);
			assign(y,v,v,y-v*k);
		}
		if(a<0)a=-a,x=-x,y=-y;
		return a;
	}

	template<class T>T mod_inv(T a,T m){
		T x,y,g=exgcd(a,m,x,y);
		if(g!=1)return -1;
		return(x%m+m)%m;
	}

	template<class T>T mod_inv_prime(T a,T p){ return modpow(a,p-2,p); }

	template<class mint=modint998244353>
	class combination{
		private:
			using tint = long long;
			vector<mint>invprod,prod;
			vector<tint>inv;
			const unsigned long long M;
		public:
		combination(int n=1):invprod(2,1),prod(2,1),inv(2,0),M(mint(-1).val()+1){
			inv[1]=1;
			if(n>1)PreCalc(n);
		}
		void PreCalc(int n){
			int presize=inv.size();
			if(presize>=n+1)return;
			inv.resize(n+1);
			prod.resize(n+1);
			invprod.resize(n+1);
			for(int i=presize;i<=n;i++){
				prod[i]=prod[i-1]*i;
				inv[i]=(((M/i)*(-inv[M%i]))+M)%M;
				invprod[i]=invprod[i-1]*inv[i];
			}
		}
		mint factorial(size_t n){
			PreCalc(n);
			return prod[n];
		}
		mint invfact(size_t n){
			PreCalc(n);
			return invprod[n];
		}
		mint P(size_t n,size_t k){
			if(n<k) return 0;
			PreCalc(n);
			return prod[n]*invprod[n-k];
		}
		mint C(size_t n,size_t k){
			if(n<k) return 0;
			PreCalc(n);
			return prod[n]*invprod[n-k]*invprod[k];
		}
		mint H(size_t n,size_t k){
			if(n==0) return mint(k!=0);
			PreCalc(n);
			return C(n+k-1,k);
		}
	};
}
#endif
	/**
	 * miller rabin
	 */
	bool is_prime(uint64_t p){
		if(p<=1)return false;
		for(auto s:{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101}){
			if(p==s)return true;
			if(p%s==0)return false;
		}
		uint64_t d=(p-1)>>countr_zero(p-1);
		auto ok=[&](uint64_t a)-> bool {
			uint64_t y=elsie::modpow(a,d,p);
			uint64_t t=d;
			while(y!=1&&y!=p-1&&t!=p-1){
				y=__uint128_t(y)*y%p;
				t<<=1;
			}
			return !(y!=p-1&&t%2==0);
		};
		if(p<(1ull<<32)){
			for(uint64_t a:{2,7,61})
				if(!ok(a))return false;
		}else{
			for(uint64_t a:{2,325,9375,28178,450775,9780504,1795265022}){
				if(p<=a)return true;
				if(!ok(a))return false;
			}
		}
		return true;
	}

void slv(){
	STR(s);
	if(s.size()<18){
		out(0);
		yn(is_prime(stoull(s)));
	}else{
		out((s.back()-'0')&1);
		no;
	}
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cout<<fixed<<setprecision(15);
	slv();
}
yukicoder

結果

ソースコード
