結果
| 問題 |
No.2972 確率的素数判定
|
| ユーザー |
 clever-elsie
|
| 提出日時 | 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();
}