結果
問題 |
No.2972 確率的素数判定
|
ユーザー |
|
提出日時 | 2025-03-18 22:28:05 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 86 ms / 2,000 ms |
コード長 | 20,095 bytes |
コンパイル時間 | 2,874 ms |
コンパイル使用メモリ | 240,752 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-18 22:28:13 |
合計ジャッジ時間 | 7,063 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#ifndef ELSIE_LOCAL_H #define ELSIE_LOCAL_H #ifndef ELSIE_MISC_HEADER #define ELSIE_MISC_HEADER #if __has_include(<atcoder/modint>) #include "atcoder/modint" using namespace atcoder; using mint=modint998244353; using mint1=modint1000000007; #endif #include <limits> #include <new> #include <initializer_list> #include <compare> #include <concepts> #include <utility> #include <bitset> #include <tuple> #include <type_traits> #include <functional> #include <chrono> #include <array> #include <deque> #include <list> #include <queue> #include <vector> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #include <iterator> #include <ranges> #include <algorithm> #include <bit> #include <random> #include <numeric> #include <numbers> #include <iostream> #include <ios> #include <streambuf> #include <iomanip> #include <sstream> #include <regex> #include <cassert> #include <cctype> #include <climits> #include <cmath> #include <cstdarg> #include <cstddef> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> using namespace std; using namespace chrono; using std::cin; using std::cout; using sstream=stringstream; #endif #ifndef ELSIE_MISC_DEFINE #define ELSIE_MISC_DEFINE #define RET return #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 _SEL4(_1,_2,_3,_4,name,...) name #define _SEL3(_1,_2,_3,name,...) name #define _REP4(i,s,n,st) for(long 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(long 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 iter(...) _SEL3(__VA_ARGS__,_ITER3,_ITER2)(__VA_ARGS__) #define cter(...) _SEL3(__VA_ARGS__,_CTER3,_CTER2)(__VA_ARGS__) #endif #ifndef ELSIE_MISC_CONST #define ELSIE_MISC_CONST #define NL cout<<'\n' #define npi numbers::pi constexpr int64_t inf=1ll<<60,minf=-inf; constexpr int32_t inf32=1ll<<30,minf32=-inf32; constexpr char sep='\n'; constexpr array<pair<int32_t,int32_t>,8>dc={{{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}}}; #define yes cout<<"Yes\n" #define no cout<<"No\n" #define yn(c) (c)?yes:no #endif #if __cplusplus > 202002L #ifndef ELSIE_MISC_FUNC #define ELSIE_MISC_FUNC 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 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) 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 _BISECT4(_1,_2,_3,_4,name,...) name #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(...) _BISECT4(__VA_ARGS__,_LB_BEXG,_LB_BEX)(__VA_ARGS__) #define ub(...) _BISECT4(__VA_ARGS__,_UB_BEXG,_UB_BEX)(__VA_ARGS__) #define TP template<class T,class U,typename cp=less<U>> template<class T,class U>concept LUBI= same_as<T,vector<U>>||same_as<T,deque<U>>||is_array_v<T>; #define RL requires LUBI<T,U> TP size_t lbi(const T&v,const U&x,cp cmp=cp())RL{RET lb(A(v),x,cmp)-begin(v);} TP size_t ubi(const T&v,const U&x,cp cmp=cp())RL{RET ub(A(v),x,cmp)-begin(v);} TP size_t lbi(size_t i,const T&v,const U&x,cp cmp=cp())RL{RET lb(i+A(v),x,cmp)-begin(v);} TP size_t ubi(size_t i,const T&v,const U&x,cp cmp=cp())RL{RET ub(i+A(v),x,cmp)-begin(v);} TP size_t lbi(const T&v,size_t i,const U&x,cp cmp=cp())RL{RET lb(I(v,i),x,cmp)-begin(v);} TP size_t ubi(const T&v,size_t i,const U&x,cp cmp=cp())RL{RET ub(I(v,i),x,cmp)-begin(v);} TP size_t lbi(size_t i,const T&v,size_t e,const U&x,cp cmp=cp())RL{RET lb(i+I(v,e),x,cmp)-begin(v);} TP size_t ubi(size_t i,const T&v,size_t e,const U&x,cp cmp=cp())RL{RET ub(i+I(v,e),x,cmp)-begin(v);} #undef TP #undef RL #define TP template<integral T> #define MT make_unsigned_t<T> TP constexpr int32_t pcnt(T p){return popcount(MT(p));} TP constexpr int32_t lsb(T p){return countr_zero(MT(p));} TP constexpr int32_t msb(T p){return sizeof(T)*8-1-countl_zero(MT(p));} template<int32_t 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; } #undef TP #undef MT #endif #ifndef ELSIE_STD_IO #define ELSIE_STD_IO #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 VIT(a,n) vit 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 #ifdef LOCAL #define dput(...) dos=&cerr;out(__VA_ARGS__);dos=&cout #else #define dput(...) #endif template<class T>concept Lint=same_as<T,__int128_t>||same_as<T,__uint128_t>; template<class T>concept Itrabl=requires(const T&x){x.begin();x.end();}&&!std::is_same_v<T,string>; template<class T>concept IItrabl=Itrabl<T>&&Itrabl<typename T::value_type>; template<class T>concept ModInt=requires(const T&x){x.val();}; template<class T>concept NLobj=Itrabl<T>||std::is_same_v<T,string>; istream&operator<<(istream&is,__float128&x){double y;is>>y;x=y;return is;} ostream&operator<<(ostream&os,const __float128&x){return os<<static_cast<double>(x);} template<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; __uint128_t v=val; if(vsign&&val!=numeric_limits<T>::min())v=1+~(__uint128_t)val; do{ *(--d)="0123456789"[v%10]; v/=10; }while(v!=0); if(vsign)*(--d)='-'; ptrdiff_t len=end(_O128)-d; if(dst.rdbuf()->sputn(d,len)!=len)dst.setstate(ios_base::badbit); return dst; } template<Lint T>istream&operator>>(istream&src,T&val) { string s;src>>s; bool is_neg=numeric_limits<T>::is_signed&&s.size()>0&&s[0]=='-'; for(val=0;const auto&x:s|views::drop(is_neg))val=10*val+x-'0'; if(is_neg)val*=-1; return src; } template<ModInt T>istream&operator>>(istream&is,T&v){int64_t x;is>>x;v=x;return is;} template<class T,class U>istream&operator>>(istream&is,pair<T,U>&v){return is>>v.first>>v.second;} template<Itrabl T>istream&operator>>(istream&is,T&v){for(auto&&x:v)is>>x;return is;} template<class T>void in(T&a){cin>>a;} template<class T,class... Ts>void in(T&a,Ts&... b){in(a);in(b...);} template<class T,class U>vector<pair<T,U>>zip(size_t n,size_t m){ vector<pair<T,U>>r(min(n,m)); iter(x,y,r)in(x); iter(x,y,r)in(y); return move(r); } template<class T,class U>vector<pair<T,U>>zip(size_t n){return move(zip<T,U>(n,n));} template<ModInt T>ostream&operator<<(ostream&os,const T&v){return os<<v.val(); } template<class T,class U>ostream&operator<<(ostream&os,const pair<T,U>&v){return os<<'('<<v.first<<','<<v.second<<')';} template<Itrabl T>ostream&operator<<(ostream&os,const T&v){size_t cnt=0;cter(x,v)os<<x<<(++cnt<v.size()?" ":"");return os;} template<IItrabl T>ostream&operator<<(ostream&os,const T&v){size_t cnt=0;cter(x,v)os<<x<<(++cnt<v.size()?"\n":"");return os;} inline ostream*dos=&cout; inline int32_t OFLG; // 0:first, 1:notNLobj, 2:NLobj template<class T>void _out(const T&a){if(OFLG)(*dos)<<"0 \n"[OFLG]<<a;else(*dos)<<a;OFLG=1;} template<NLobj T>void _out(const T&a){(*dos)<<(OFLG?"\n":"")<<a;OFLG=2;} template<class T,class...Ts>void _out(const T&a,const Ts&... b){_out(a);_out(b...);} template<class... Ts>void out(const Ts&... v){OFLG=0;_out(v...);(*dos)<<sep;} #endif #endif #endif #ifndef ELSIE_PRIMITIVE_ROOT #define ELSIE_PRIMITIVE_ROOT #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);} // std::ceil(std::sqrtl(x:u64))が64bit精度で40%高速なので,long double 80bitならそちらを使うべき template<bool internal_invocate=false> inline uint64_t sqrt_ceil(uint64_t x){ if constexpr(!internal_invocate){ // sqrt_floorからの呼出しではここをスキップする if(x>uint64_t(UINT32_MAX)*UINT32_MAX)return 1ull<<32; else if(x<2)return x!=0; } uint64_t nx,y=min<uint64_t>((1ULL<<((64-countl_zero(x))>>1)+1)-1,UINT32_MAX); y-=(y*y-x)/(y<<1); y-=(y*y-x)/(y<<1); y-=(y*y-x)/(y<<1); y-=(y*y-x)/(y<<1); y-=(y*y-x)/(y<<1); nx=y-(y*y-x)/(y<<1); while(nx!=y){ y=nx; nx=y-(y*y-x)/(y<<1); if(nx==y)break; } return y+(y*y<x?1:(y-1)*(y-1)>=x?-1:0); } inline uint64_t sqrt_floor(uint64_t x){ if((uint64_t)UINT32_MAX*UINT32_MAX<=x)return UINT32_MAX; else if(x<4)return x!=0; uint64_t y=sqrt_ceil<true>(x); return y-(y*y!=x); } using u128=__uint128_t; using u64 = uint64_t; inline __uint128_t mul64to128(u64 a,u64 b){ u64 hi,lo; asm("mulq %3" :"=a"(lo),"=d"(hi):"a"(a),"r"(b)); return((__uint128_t)(hi)<<64)+lo; } inline pair<u128,u128>mul128(u128 a,u128 b){ constexpr static u128 Lfilter=0xFFFF'FFFF'FFFF'FFFFull; u64 x1=a>>64,x0=a&Lfilter; u64 y1=b>>64,y0=b&Lfilter; u128 z2=mul64to128(x1,y1),z1=mul64to128(x1,y0)+mul64to128(x0,y1),z0=mul64to128(x0,y0); u128 lower=z0+(z1<<64); return{z2+(z1>>64)+(lower<z0),lower}; } inline u128 rem256(pair<u128,u128>x,u128 mod){ u128 rem32=(u128(1)<<32)%mod; u128 rem64=rem32*rem32%mod; u128 rem128=rem64*rem64%mod; auto&&[a,b]=x; a%=mod,b%=mod; return(a*rem128%mod+b)%mod; } 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; } template<integral T,class U=make_unsigned_t<T>> constexpr T modpow(T a,U b,U mod){ if constexpr(is_same_v<U,__uint128_t>){ // mod=2^64専用 constexpr __uint128_t filter=uint64_t(-1); a%=mod; __uint128_t ret=1; if(a<0)a+=mod; while(b){ ret=(b&1?ret*a&filter:ret); a=a*a&filter; b>>=1; } return uint64_t(ret&filter); }else{ __int128_t k=a%mod,ret=1; if(k<0)k+=mod; while(b){ ret=(b&1?ret*k%mod:ret); 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,r=a%b; assign(a,b,b,r); assign(x,u,u,x-u*k); assign(y,v,v,y-v*k); } if constexpr(is_signed_v<T>) 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(int64_t 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(int64_t n){ size_t presize=inv.size(); if(presize>=n+1)return; inv.resize(n+1); prod.resize(n+1); invprod.resize(n+1); for(int64_t 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); } }; class barret32{ uint64_t M,iM; public: barret32():M(0),iM(0){} barret32(uint32_t m):M(m),iM(uint64_t(-1)/m+1){} void set(uint32_t m){ M=m,iM=uint64_t(-1)/m+1; } uint32_t umod()const{ return M; } uint32_t mul(uint32_t a,uint32_t b)const{ uint64_t z=(uint64_t)a*b; uint64_t x=((__uint128_t)z*iM>>64); uint64_t y=x*M; return(uint32_t)(z-y+(z<y?M:0)); } }; class barret64{ __uint128_t M,iM; public: barret64():M(0),iM(0){} barret64(uint64_t m):M(m),iM(__uint128_t(-1)/M+1){} uint64_t umod(){ return M; } uint64_t mul(uint64_t a,uint64_t b){ __uint128_t z=mul64to128(a,b); __uint128_t x=mul128(z,iM).first; __uint128_t y=x*M; return(uint64_t)(z-y+(z<y?M:0)); } }; } #endif namespace elsie{ using namespace std; // O(\sqrt{n}) constexpr uint64_t eular_totient(uint64_t n){ uint64_t r=n; for(uint64_t i=2;i*i<=n;++i){ if(n%i==0){ r-=r/i; while(n%i==0)n/=i; } } if(n>1)r-=r/n; return r; } vector<uint64_t>quotients(uint64_t n){ using u64=uint64_t; vector<u64>ret; for(int x=n;x>0;){ u64 q=n/x; ret.push_back(q); x=n/(q+1); } return ret; } /** * miller rabin * 2^64を受け取れるように一応しているが,実際に判定できるのはuint64_tだけ */ template<class T> constexpr bool is_prime(T p)requires is_integral_v<T>||same_as<T,__int128_t>||same_as<T,__uint128_t>{ if constexpr(sizeof(T)>8) return false; else{ if(p<=1)return false; for(const 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==(T)s)return true; if(p%s==0)return false; } uint64_t d=({ uint64_t r=0; if constexpr(sizeof(T)<=8) r=(p-1)>>countr_zero(make_unsigned_t<T>(p)-1); else{ T s=p-1; while((s&1)==0)s>>=1,++r; } r; }); auto ok=[&](uint64_t a)-> bool { uint64_t y=modpow<uint64_t>(a,d,uint64_t(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; }; 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; } // endif constexpr } /** * pollard's rho O(n^{1/4}) */ vector<uint64_t>factorize(uint64_t m){ if(m==1)return {}; if(is_prime<uint64_t>(m))return{m}; auto pollard_rho=[&](auto pollard_rho,uint64_t n)->uint64_t { if(~n&1)return 2; if(is_prime(n))return n; uint64_t x,y,ys,g,q,r,k,m=uint64_t(pow<double>(double(n),1.0/8.0))+1; for(uint64_t c=1;c<n;++c){ auto f=[&](__uint128_t a){return(a*a+c)%n;}; y=k=0;g=q=r=1; while(g==1){ x=y; while(k<3*r/4)y=f(y),++k; while(k<r&&g==1){ ys=y; for(uint64_t _=0;_<m&&_+k<r;++_) y=f(y),q=__uint128_t(q)*(x>y?x-y:y-x)%n; g=gcd(q,n); k+=m; } k=r; r<<=1; } if(g==n){ g=1,y=ys; while(g==1) y=f(y),g=gcd(x>y?x-y:y-x,n); } if(g==n)continue; if(is_prime(g))return g; else if(is_prime(n/g))return n/g; else return pollard_rho(pollard_rho,g); } return 0; }; vector<uint64_t>ret; ret.reserve(64); while(m>1&&!is_prime(m)) for(uint64_t p=pollard_rho(pollard_rho,m);m%p==0;m/=p) ret.push_back(p); if(m>1)ret.push_back(m); sort(begin(ret),end(ret)); return ret; } int64_t primitive_root(uint64_t n){ if(n==2)return 1; if(n==3)return 2; vector<uint64_t> factor=factorize(n-1); factor.erase(unique(begin(factor),end(factor)),end(factor)); random_device seed; mt19937_64 engine(seed()); uniform_int_distribution<uint64_t>rng(2,n-2); for(uint64_t g=1,ok=1;1;g=rng(engine),ok=1){ for(const auto&q:factor) if(modpow(g,(n-1)/q,n)==1){ok=0;break;} if(ok)return g; } return -1; } } #endif #ifndef ELSIE_ALIAS #define ELSIE_ALIAS 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 gr=greater<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 it=int32_t; using i8=int8_t; using u8=uint8_t; using i16=int16_t; using u16=uint16_t; using i32=int32_t; using u32=uint32_t; using i64=int64_t; using u64=uint64_t; using i128=__int128_t; using u128=__uint128_t; using intw=__int128_t; using uintw=__uint128_t; using f32=float; using f64=double; using f128=__float128; using vi=vc<i64>; using vit=vc<it>; using vb=vc<bool>; using pi=pair<i64,i64>; using pit=pair<it,it>; using str=string; using vs=vc<str>; using pqgp=pqg<pi>; #define int i64 #define itn i64 #define LL long long #endif array<it,1'00'001> pc; void slv(){ INT(n,P,Q); long double p=(long double)P/100.0, q=(long double)Q/100.0; long double Pp=(long double)pc[n]/n; long double y=p*Pp+(1-Pp)*(1-q); out(Pp/y*p); } signed main(){ cin.tie(0)->sync_with_stdio(0); cout<<fixed<<setprecision(15); pc.fill(0); rep(i,2,1'00'001) pc[i]=pc[i-1]+elsie::is_prime(i); INT(t); rep(t) slv(); }