結果
問題 | No.2125 Inverse Sum |
ユーザー | 👑 p-adic |
提出日時 | 2022-11-19 00:52:15 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 20 ms / 2,000 ms |
コード長 | 3,333 bytes |
コンパイル時間 | 2,112 ms |
コンパイル使用メモリ | 209,440 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-20 05:04:40 |
合計ジャッジ時間 | 3,316 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 1 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 1 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 1 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 1 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 1 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 20 ms
5,376 KB |
testcase_28 | AC | 16 ms
5,376 KB |
testcase_29 | AC | 12 ms
5,376 KB |
testcase_30 | AC | 2 ms
5,376 KB |
testcase_31 | AC | 16 ms
5,376 KB |
testcase_32 | AC | 4 ms
5,376 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using uint = unsigned int; using ll = long long; #define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define CEXPR( LL , BOUND , VALUE ) constexpr const 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 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 REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) #define QUIT return 0 #define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT class NM { public : ll m_N; ll m_M; inline NM( const ll& N = 0 , const ll& M = 0 ) : m_N( N ) , m_M( M ) {}; }; inline bool operator<( const NM& NM0 , const NM& NM1 ) { return NM0.m_N < NM1.m_N; } void SetPrimeFactorisation( const uint& n , vector<uint>& P , vector<uint>& exponent ) { uint n_copy = n; uint p = 2; if( n_copy % p == 0 ){ P.push_back( p ); exponent.push_back( 1 ); uint& exponent_back = exponent.back(); n_copy /= p; while( n_copy % p == 0 ){ exponent_back++; n_copy /= p; } } p++; while( n_copy != 1 ){ if( n_copy % p == 0 ){ P.push_back( p ); exponent.push_back( 1 ); uint& exponent_back = exponent.back(); n_copy /= p; while( n_copy % p == 0 ){ exponent_back++; n_copy /= p; } } p += 2; if( p * p > n_copy ){ break; } } if( n_copy != 1 ){ P.push_back( n_copy ); exponent.push_back( 1 ); } return; } int main() { CEXPR( ll , bound_PQ , 1000000000 ); CIN_ASSERT( P , 1 , bound_PQ ); CIN_ASSERT( Q , 1 , bound_PQ ); vector<uint> prime{}; vector<uint> exponent{}; if( Q == 1 ){ prime.push_back( 1 ); exponent.push_back( 0 ); } else { SetPrimeFactorisation( Q , prime , exponent ); } uint size = exponent.size(); ll count = 1; FOR( i , 0 , size ){ uint& exponent_i = exponent[i]; exponent_i *= 2; count *= exponent_i + 1; } ll Q2 = Q * Q; vector<uint> curr( size ); ll div_N , div_M; vector<NM> answer{}; FOR( c , 0 , count ){ div_N = 1; FOR( i , 0 , size ){ uint& curr_i = curr[i]; uint& prime_i = prime[i]; REPEAT( curr_i ){ div_N *= prime_i; } } div_M = Q2 / div_N; div_N += Q; div_M += Q; if( div_N % P == 0 && div_M % P == 0 ){ answer.push_back( NM( div_N / P , div_M / P ) ); } uint i = 0; bool updating = c + 1 < count; while( updating ){ uint& curr_i = curr[i]; if( curr_i < exponent[i] ){ curr_i++; updating = false; } else { curr_i = 0; i++; } } } uint T = answer.size(); cout << T << "\n"; sort( answer.begin() , answer.end() ); FOR( t , 0 , T ){ NM& NMt = answer[t]; cout << NMt.m_N << " " << NMt.m_M << "\n"; } QUIT; }