結果

問題 No.2972 確率的素数判定
ユーザー 👑 p-adicp-adic
提出日時 2023-08-18 12:15:08
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 30 ms / 2,000 ms
コード長 5,846 bytes
コンパイル時間 4,704 ms
コンパイル使用メモリ 274,860 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-27 18:53:33
合計ジャッジ時間 6,272 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 4 ms
5,248 KB
testcase_16 AC 29 ms
5,248 KB
testcase_17 AC 29 ms
5,248 KB
testcase_18 AC 30 ms
5,248 KB
testcase_19 AC 30 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAIN main
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#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 <typename INT , INT val_limit , int length_max = val_limit>
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 <typename INT , INT val_limit , int length_max = val_limit>
class PrimeCounting
{

private:
  int m_val[val_limit];

public:
  inline constexpr PrimeCounting( const PrimeEnumeration<INT,val_limit,length_max>& pe );

  // min(i以下の素数の個数,length_max)を返す。
  inline constexpr const int& Pi( const int& i ) const;

};

template <typename INT , INT val_limit , int length_max> inline constexpr PrimeEnumeration<INT,val_limit,length_max>::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 <typename INT , INT val_limit , int length_max> inline constexpr const INT& PrimeEnumeration<INT,val_limit,length_max>::Get( const int& n ) const { assert( n < m_length ); return m_val[n]; }
template <typename INT , INT val_limit , int length_max> inline constexpr const bool& PrimeEnumeration<INT,val_limit,length_max>::IsComposite( const int& i ) const { assert( i < val_limit ); return m_is_composite[i]; }
template <typename INT , INT val_limit , int length_max> inline constexpr const int& PrimeEnumeration<INT,val_limit,length_max>::length() const noexcept { return m_length; }

template <typename INT , INT val_limit , int length_max> inline constexpr PrimeCounting<INT,val_limit,length_max>::PrimeCounting( const PrimeEnumeration<INT,val_limit,length_max>& 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 <typename INT , INT val_limit , int length_max> inline constexpr const int& PrimeCounting<INT,val_limit,length_max>::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<int,bound_N+1,9592> pe{};
  constexpr const PrimeCounting<int,bound_N+1,9592> 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;
}
0