#904642 (C++17(gcc12)) No.2972 確率的素数判定

提出ソース
結果

問題	No.2972 確率的素数判定
ユーザー	👑 p-adic
提出日時	2023-08-18 12:15:08
言語	C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
結果	AC
実行時間	31 ms / 2,000 ms
コード長	5,846 bytes
コンパイル時間	17,132 ms
コンパイル使用メモリ	332,976 KB
最終ジャッジ日時	2025-02-16 09:04:12
ジャッジサーバーID （参考情報）	judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 20
権限があれば一括ダウンロードができます
ソースコード

raw source code
プレゼンテーションモードにする

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#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;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
yukicoder

結果

ソースコード
