#ifdef DEBUG #define _GLIBCXX_DEBUG #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ); signal( SIGABRT , &AlertAbort ) #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE ) #define CERR( MESSAGE ) cerr << MESSAGE << endl; #define COUT( ANSWER ) cout << ANSWER << endl #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック: " << ( MIN ) << ( ( MIN ) <= A ? "<=" : ">" ) << A << ( A <= ( MAX ) ? "<=" : ">" ) << ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) ) #else #pragma GCC optimize ( "O3" ) #pragma GCC optimize( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE ) #define CERR( MESSAGE ) #define COUT( ANSWER ) cout << ANSWER << "\n" #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) ) #endif #include using namespace std; using ll = long long; #define MAIN main #define TYPE_OF( VAR ) decay_t #define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE #define CIN( LL , A ) LL A; cin >> A #define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX ) #define CIN_ASSERT( A , MIN , MAX ) TYPE_OF( MAX ) A; SET_ASSERT( A , MIN , MAX ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES ) #define QUIT return 0 #ifdef DEBUG inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); } #endif // m_lengthの値は // val_limit = 316 -> 65 // val_limit = 10^3 -> 168 // val_limit = 10^4 -> 1229 // val_limit = 10^5 -> 9592 // val_limit = 2×10^5 -> 17984 // 以下コンパイル畤計算の上限回数262144を超過。非constexpr変数を初期化すればよい。 // val_limit = 316228 -> 27293(実行時間4[ms]) // val_limit = 10^6 -> 78498(実行時間8[ms]) // val_limit = 10^7 -> 664579(実行時間93[ms]) // val_limit = 10^8 -> 5761455(実行時間2839[ms]) template class PrimeEnumeration { private: bool m_is_composite[val_limit]; INT m_val[length_max]; int m_length; public: inline constexpr PrimeEnumeration(); // 1+n個目の素数を返す。 inline constexpr const INT& Get( const int& n ) const; // length_max個目の素数までで割り切れる合成数であるか否かを判定する。 inline constexpr const bool& IsComposite( const int& i ) const; // val_limit未満の素数の個数Pi(val_limit)を返す。 inline constexpr const int& length() const noexcept; }; template class PrimeCounting { private: int m_val[val_limit]; public: inline constexpr PrimeCounting( const PrimeEnumeration& pe ); // min(i以下の素数の個数,length_max)を返す。 inline constexpr const int& Pi( const int& i ) const; }; template inline constexpr PrimeEnumeration::PrimeEnumeration() : m_is_composite() , m_val() , m_length( 0 ) { for( INT i = 2 ; i < val_limit ; i++ ){ if( ! m_is_composite[i] ){ INT j = i; while( ( j += i ) < val_limit ){ m_is_composite[j] = true; } m_val[m_length++] = i; if( m_length >= length_max ){ break; } } } } template inline constexpr const INT& PrimeEnumeration::Get( const int& n ) const { assert( n < m_length ); return m_val[n]; } template inline constexpr const bool& PrimeEnumeration::IsComposite( const int& i ) const { assert( i < val_limit ); return m_is_composite[i]; } template inline constexpr const int& PrimeEnumeration::length() const noexcept { return m_length; } template inline constexpr PrimeCounting::PrimeCounting( const PrimeEnumeration& pe ) : m_val{ 0 , 0 } { int temp = 0; for( int i = 2 ; i < val_limit ; i++ ){ m_val[i] = pe.IsComposite( i ) ? temp : ++temp; } } template inline constexpr const int& PrimeCounting::Pi( const int& i ) const { assert( i < val_limit ); return m_val[i]; } int MAIN() { UNTIE; DEXPR( int , bound_N , 100000 , 100 ); // 0が5個 constexpr const PrimeEnumeration pe{}; constexpr const PrimeCounting pc{ pe }; DEXPR( int , bound_T , 100000 , 100 ); CIN_ASSERT( T , 1 , bound_T ); CEXPR( int , bound_PQ , 100 ); CEXPR( ll , digits , 10000000000 ); // 0が10個 string one = "1"; string zero = "0"; string zero_point = "0."; REPEAT( T ){ CIN_ASSERT( N , 1 , bound_N ); CIN_ASSERT( P , 0 , bound_PQ ); CIN_ASSERT( Q , 0 , bound_PQ ); assert( ( 1 < N && 0 < P ) || Q < bound_PQ ); const int& pi_N = pc.Pi( N ); int P_pi_N = P * pi_N; if( Q == bound_PQ ){ COUT( one ); } else if( P_pi_N == 0 ){ COUT( zero ); } else { ll answer = ( P_pi_N * digits ) / ( P_pi_N + ( 100 - Q ) * ( N - pi_N ) ) + digits; while( answer % 10 == 0 ){ answer /= 10; } COUT( zero_point + to_string( answer ).substr( 1 ) ); } } QUIT; }