結果

問題 No.2359 A in S ?
ユーザー 👑 p-adic
提出日時 2023-06-24 00:43:07
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 405 ms / 2,000 ms
コード長 36,173 bytes
コンパイル時間 12,417 ms
コンパイル使用メモリ 290,612 KB
最終ジャッジ日時 2025-02-15 01:48:50
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

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( ANSWER ) cerr << ANSWER << endl;
#define LIBRARY_SEARCH if( LibrarySearch() != 0 ){ QUIT; };
#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( ANSWER )
#define LIBRARY_SEARCH
#endif
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) )
#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 ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX )
#define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )
#define GETLINE( A ) string A; getline( cin , A )
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )
#define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- )
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define QUIT return 0
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT
#define SET_PRECISION( PRECISION ) cout << fixed << setprecision( PRECISION )
#define DOUBLE( PRECISION , ANSWER ) SET_PRECISION << ( ANSWER ) << "\n"; QUIT
inline void AlertAbort( int n ) { cerr <<
    "abortassert" << endl; }
template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : -a; }
template <typename T> inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : ( a % p ) + p; }
#define POWER( ANSWER , ARGUMENT , EXPONENT ) \
static_assert( ! is_same<TYPE_OF( ARGUMENT ),int>::value && ! is_same<TYPE_OF( ARGUMENT ),uint>::value ); \
TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \
{ \
TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT ); \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO ) \
ll ANSWER{ 1 }; \
{ \
ll ARGUMENT_FOR_SQUARE_FOR_POWER = ( MODULO + ( ( ARGUMENT ) % MODULO ) ) % MODULO; \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define FACTORIAL_MOD( ANSWER , ANSWER_INV , INVERSE , MAX_INDEX , CONSTEXPR_LENGTH , MODULO ) \
static ll ANSWER[CONSTEXPR_LENGTH]; \
static ll ANSWER_INV[CONSTEXPR_LENGTH]; \
static ll INVERSE[CONSTEXPR_LENGTH]; \
{ \
ll VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \
ANSWER[0] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL; \
FOREQ( i , 1 , MAX_INDEX ){ \
ANSWER[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= i ) %= MODULO; \
} \
ANSWER_INV[0] = ANSWER_INV[1] = INVERSE[1] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \
FOREQ( i , 2 , MAX_INDEX ){ \
ANSWER_INV[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= INVERSE[i] = MODULO - ( ( ( MODULO / i ) * INVERSE[MODULO % i] ) % MODULO ) ) %= MODULO
          ; \
} \
} \
//
// EXPRESSIONANSWER調EXPRESSION >= TARGET
#define BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET , INEQUALITY , UPDATE_U , UPDATE_L , UPDATE_ANSWER ) \
static_assert( ! is_same<TYPE_OF( TARGET ),uint>::value && ! is_same<TYPE_OF( TARGET ),ull>::value ); \
ll ANSWER = MINIMUM; \
if( MINIMUM <= MAXIMUM ){ \
ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \
ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM; \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \
while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \
CERR( VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << "=" <<
          VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH INEQUALITY 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_U = UPDATE_U; \
} else { \
VARIABLE_FOR_BINARY_SEARCH_L = UPDATE_L; \
} \
ANSWER = UPDATE_ANSWER; \
} \
CERR( VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << (
        EXPRESSION > TARGET ? ">0" : EXPRESSION < TARGET ? "<0" : "0" ) ); \
} else { \
CERR( MINIMUM << ">" << MAXIMUM << "" ); \
} \
// 調EXPRESSION >= TARGET
#define BS1( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET , >= , ANSWER , ANSWER + 1 , ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) /
      2 ) \
// 調EXPRESSION <= TARGET
#define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET , > , ANSWER - 1 , ANSWER , ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U
      ) / 2 ) \
// 調EXPRESSION >= TARGET
#define BS3( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET , < , ANSWER - 1 , ANSWER , ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U
      ) / 2 ) \
// 調EXPRESSION <= TARGET
#define BS4( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET , <= , ANSWER , ANSWER + 1 , ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) /
      2 ) \
//
#define TE template
#define TY typename
#define US using
#define ST static
#define IN inline
#define CL class
#define PU public
#define OP operator
#define CE constexpr
#define CO const
#define NE noexcept
#define RE return
#define WH while
#define VO void
#define VE vector
#define LI list
#define BE begin
#define EN end
#define SZ size
#define MO move
#define TH this
#define CRI CO int&
#define CRUI CO uint&
#define CRL CO ll&
int QuitLibrarySearch( const int& problems_size ){
cerr << "" << problems_size - 1 << "";
CERR( "" );
CERR( "" );
return -1;
}
int LibrarySearch( int num = -1 )
{
vector<string> problems =
{
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
""
};
CEXPR( int , num_graph , 5 );
CEXPR( int , num_subsequence_sum , 6 );
CEXPR( int , num_game , 8 );
int problems_size = problems.size();
string reply{};
if( num == -1 ){
CERR( "[y/n]" );
CIN( string , reply );
if( reply == "n" ){
CERR( "" );
CERR( "" );
return 0;
} else if( reply != "y" ){
CERR( "y/n" );
CERR( "" );
CERR( "" );
return -1;
}
CERR( "" );
CERR( "" );
CERR( "" );
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
cin >> num;
}
CERR( "" );
int num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "[y/n/c]" );
cin >> reply;
CERR( "" );
if( reply == "y" ){
CERR( "OEIS" );
CERR( "https://oeis.org/?language=japanese" );
CERR( "" );
CERR( "" );
CERR( "- 調" );
CERR( "- p使" );
CERR( "- pp" );
CERR( " " );
CERR( "" );
} else if( reply == "n" ){
CERR( "" );
} else {
CERR( "y/n" );
CERR( "" );
CERR( "" );
return -1;
}
CERR( "" );
CERR( "" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
problems =
{
"" ,
"" ,
"" ,
"" ,
""
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- +使BIT" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\Template")
CERR( "- 使BIT" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\IntervalMax\\Template" );
CERR( "- *使BIT" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\Template\\Monoid" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\Monoid" );
CERR( "- (*,\\cdot)使" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\Dual" );
CERR( "- (+,\\cdot)使" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\LazyEvaluation" );
CERR( "- 使" );
CERR( " \\Mathematics\\Function\\Encoder" );
CERR( "- (+,max)使" );
CERR( " " );
CERR( " B_qmax(A_i,B_q)" );
CERR( " - A'={(A_i,i)|i}O(N log N)" );
CERR( " - (B_q,q)_qB'O(Q log Q)" );
CERR( " - NC=(0,...,0)O(N)" );
CERR( " B'(B_q,q)" );
CERR( " A'A_i<B_qi" );
CERR( " - A'(A_i,i)O(N)" );
CERR( " - A_i0O(N log N)" );
CERR( " - C_i1O(log N)" );
CERR( " - A+C×B_qO(log N)" );
CERR( " O((N + Q)log N + Q log Q)" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "fx" );
CERR( "- ixX(i)" );
CERR( "- ixi+1xdX(i)" );
CERR( "" );
CERR( "- O(sum_i X(i) dX(i))fxO(1)ix" );
CERR( "- O(N log_2 X)fxO(N)x調x" );
CERR( "- O(N log_2 N)xfxO(log_2 N)" );
CERR( " x" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( " " );
CERR( "- " );
CERR( " " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "gcdmax" );
CERR( "" );
} else {
return LibrarySearch( num = num_subsequence_sum );
}
} else if( num == num_temp++ ){
CERR( "" );
problems =
{
"" ,
"" ,
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( " - O(N)" );
CERR( " - O(N)" );
CERR( "- " );
CERR( "- Z" );
CERR( " https://qiita.com/Pro_ktmr/items/16904c9570aa0953bf05" );
CERR( "" );
} else {
CERR( "" );
CERR( "- O(N^2)" );
CERR( "- O(N^2)Manacher" );
CERR( " https://snuke.hatenablog.com/entry/2014/12/02/235837" );
CERR( "" );
}
} else if( num == num_temp++ ){
CERR( "" );
CERR( "" );
CERR( "- O(N^3)" );
CERR( "- O(N 2^N)" );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "- O(N^2)" );
CERR( "- O(N log_2 N)BIT" );
CERR( " \\Mathematics\\Combinatorial\\Permutation" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT" );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "i<j" );
CERR( "" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
problems =
{
"" ,
"" ,
""
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_graph );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- 調" );
CERR( "- " );
CERR( "- " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- O(HW)" );
CERR( "- O(HW)" );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( "" );
}
} else if( num == num_temp++ ){
CERR( "" );
problems =
{
"" ,
"" ,
"" ,
""
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "" );
CERR( "- BFSDijkstra" );
CERR( " \\Utility\\Search\\BreadthFirst" );
CERR( " \\Utility\\Search\\Dijkstra" );
CERR( "- " );
CERR( " - O(V^3)FloydWarshall" );
CERR( " \\Utility\\Search\\FloydWarshall" );
CERR( " - maxO(E(log_2 E + α(V)))UnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "HeldKarp" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "\\Utility\\Search\\DepthFirst" );
CERR( "\\Utility\\VLTree" );
} else {
CERR( "- 0UnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "- " );
CERR( " \\Utility\\Search\\DepthFirst" );
CERR( "- " );
CERR( "" );
}
} else if( num == num_temp++ ){
CERR( "" );
problems =
{
"" ,
""
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "NWV" );
CERR( "- B=∞" );
CERR( "- B<∞O(2^N)" );
CERR( "- B<∞O(2^{N/2} N)" );
CERR( "- B<∞O(NV)[B-V,B+V]" );
CERR( " " );
CERR( " https://stackoverflow.com/a/18949218" );
CERR( "- W10^5O((N+W)log_2 W)" );
CERR( " " );
CERR( " \\Mathematics\\Polynomial" );
} else {
CERR( "NW" );
CERR( "- O(2^N)" );
CERR( "- O(2^N)" );
CERR( "- O(2^{N/2}N)" );
CERR( " " );
CERR( "- W10^5O((N+W)log_2 W)" );
CERR( " " );
CERR( " \\Mathematics\\Polynomial" );
}
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( "- " );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace" );
CERR( "- UnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
problems =
{
"" ,
""
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_graph );
}
} else if( num == num_temp++ ){
CERR( "" );
problems =
{
"" ,
""
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "NTK" );
CERR( "- O((N + T)log_2 K)" );
CERR( " \\Mathematics\\Function\\Iteration\\Doubling" );
CERR( "- O(TN)" );
CERR( " \\Mathematics\\Function\\Iteration\\LoopDetection" );
CERR( "- O(N)" );
CERR( "" );
} else {
CERR( "" );
return LibrarySearch( num = num_graph );
}
} else if( num == num_temp++ ){
CERR( "" );
problems =
{
"" ,
"" ,
""
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "p" );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_graph );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_game );
}
}
CERR( "" );
CERR( "" );
CERR( "" );
return -1;
}
// intTint
// InitialSegmentSumuintint
// 使
// T& T::operator=( const T& )
// T& T::operator+=( const T& )
// T operator-( const T& , const T& )IntervalSum
// T operator<( const T& , const T& )BinarySearch
template <typename T , int N>
class BIT
{
private:
T m_fenwick[N + 1];
public:
inline BIT();
BIT( const T ( & a )[N] );
// const
inline T Get( const int& i ) const;
inline void Set( const int& i , const T& n );
inline BIT<T,N>& operator+=( const T ( & a )[N] );
void Add( const int& i , const T& n );
T InitialSegmentSum( const int& i_final ) const;
inline T IntervalSum( const int& i_start , const int& i_final ) const;
// operator+=T()
// InitialSegmentSum( i )ni2
int BinarySearch( const T& n ) const;
// IntervalSum( i_start , i )ti_starti2
inline int BinarySearch( const int& i_start , const T& n ) const;
};
template <typename T , int N> inline BIT<T,N>::BIT() : m_fenwick() {}
template <typename T , int N>
BIT<T,N>::BIT( const T ( & a )[N] ) : m_fenwick()
{
for( int j = 1 ; j <= N ; j++ ){
T& fenwick_j = m_fenwick[j];
int i = j - 1;
fenwick_j = a[i];
int i_lim = j - ( j & -j );
while( i != i_lim ){
fenwick_j += m_fenwick[i];
i -= ( i & -i );
}
}
}
template <typename T , int N> inline T BIT<T,N>::Get( const int& i ) const { return IntervalSum( i , i ); }
template <typename T , int N> inline void BIT<T,N>::Set( const int& i , const T& n ) { Add( i , n - IntervalSum( i , i ) ); }
template <typename T , int N> inline BIT<T,N>& BIT<T,N>::operator+=( const T ( & a )[N] ) { for( int i = 0 ; i < N ; i++ ){ Add( i , a[i] ); } return
    *this; }
template <typename T , int N>
void BIT<T,N>::Add( const int& i , const T& n )
{
int j = i + 1;
while( j <= N ){
m_fenwick[j] += n;
j += ( j & -j );
}
return;
}
template <typename T , int N>
T BIT<T,N>::InitialSegmentSum( const int& i_final ) const
{
T sum = 0;
int j = ( i_final < N ? i_final : N - 1 ) + 1;
while( j > 0 ){
sum += m_fenwick[j];
j -= j & -j;
}
return sum;
}
template <typename T , int N> inline T BIT<T,N>::IntervalSum( const int& i_start , const int& i_final ) const { return InitialSegmentSum( i_final ) -
    InitialSegmentSum( i_start - 1 ); }
// 使
// T& T::operator=( const T& )BIT使
// T& T::operator+=( const T& )
// T& operator+( const T& , const T& )
// T operator-( const T& )
// T operator-( const T& , const T& )
template <typename T , int N>
class IntervalAddBIT
{
private:
// (i-1)a_{i-1} - ia_i
BIT<T,N> m_bit_0;
// a_i - a_{i-1}
BIT<T,N> m_bit_1;
public:
inline IntervalAddBIT();
inline IntervalAddBIT( const T ( & a )[N] );
// const
inline T Get( const int& i ) const;
inline void Set( const int& i , const T& n );
inline IntervalAddBIT<T,N>& operator+=( const T ( & a )[N] );
inline void Add( const int& i , const T& n );
inline void IntervalAdd( const int& i_start , const int& i_final , const T& n );
inline T InitialSegmentSum( const int& i_final ) const;
inline T IntervalSum( const int& i_start , const int& i_final ) const;
};
template <typename T , int N> inline IntervalAddBIT<T,N>::IntervalAddBIT() : m_bit_0() , m_bit_1() {}
template <typename T , int N> inline IntervalAddBIT<T,N>::IntervalAddBIT( const T ( & a )[N] ) : m_bit_0() , m_bit_1() { operator+=( a ); }
template <typename T , int N> inline T IntervalAddBIT<T,N>::Get( const int& i ) const { return IntervalSum( i , i ); }
template <typename T , int N> inline void IntervalAddBIT<T,N>::Set( const int& i , const T& n ) { Add( i , n - IntervalSum( i , i ) ); }
template <typename T , int N> inline IntervalAddBIT<T,N>& IntervalAddBIT<T,N>::operator+=( const T ( & a )[N] ) { for( int i = 0 ; i < N ; i++ ){ Add
    ( i , a[i] ); } return *this; }
template <typename T , int N> inline void IntervalAddBIT<T,N>::Add( const int& i , const T& n ) { IntervalAdd( i , i , n ); }
template <typename T , int N> inline void IntervalAddBIT<T,N>::IntervalAdd( const int& i_start , const int& i_final , const T& n ) { m_bit_0.Add(
    i_start , - ( i_start - 1 ) * n ); m_bit_0.Add( i_final + 1 , i_final * n ); m_bit_1.Add( i_start , n ); m_bit_1.Add( i_final + 1 , - n ); }
template <typename T , int N> inline T IntervalAddBIT<T,N>::InitialSegmentSum( const int& i_final ) const { return m_bit_0.InitialSegmentSum( i_final
    ) + i_final * m_bit_1.InitialSegmentSum( i_final ); }
template <typename T , int N> inline T IntervalAddBIT<T,N>::IntervalSum( const int& i_start , const int& i_final ) const { return InitialSegmentSum(
    i_final ) - InitialSegmentSum( i_start - 1 ); }
int main()
{
UNTIE;
LIBRARY_SEARCH;
// CEXPR( int , bound_T , 100000 );
// CIN_ASSERT( T , 1 , bound_T );
CEXPR( int , bound_N , 100000 ); // 05
// CEXPR( ll , bound_N , 1000000000 ); // 09
// CEXPR( ll , bound_N , 1000000000000000000 ); // 018
CIN_ASSERT( N , 1 , bound_N );
// CEXPR( int , bound_M , 100000 ); // 05
// // CEXPR( ll , bound_M , 1000000000 ); // 09
// // CEXPR( ll , bound_M , 1000000000000000000 ); // 018
CIN_ASSERT( M , 1 , bound_N );
// REPEAT( T ){
// COUT( N );
// }
CEXPR( int , sqrt_bound_N , 316 );
int C[bound_N + 1] = {};
int D[sqrt_bound_N][bound_N + sqrt_bound_N] = {};
int L,R,X,Y,Z;
REPEAT( N ){
SET_ASSERT( L , 1 , bound_N );
SET_ASSERT( R , L , bound_N );
SET_ASSERT( X , 1 , bound_N );
SET_ASSERT( Y , 0 , X - 1 );
if( X < sqrt_bound_N ){
( ( Y < ( Z = L % X ) ? L += X : L ) -= Z ) += Y;
( ( Y <= ( Z = R % X ) ? R += X : R ) -= Z ) += Y;
int ( &DX )[bound_N + sqrt_bound_N] = D[X];
++DX[L];
--DX[R];
} else {
( ( Y < ( Z = L % X ) ? L : L -= X ) -= Z ) += Y;
while( ( L += X ) <= R ){
++C[L];
}
}
}
FOR( X , 1 , sqrt_bound_N ){
int ( &DX )[bound_N + sqrt_bound_N] = D[X];
FOR( i , X , bound_N + sqrt_bound_N ){
DX[i] += DX[i-X];
}
}
int A;
REPEAT( M ){
SET_ASSERT( A , 1 , bound_N );
int answer = C[A];
FOR( X , 1 , sqrt_bound_N ){
answer += D[X][A];
}
COUT( answer );
}
QUIT;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0