#include using namespace std; using uint = unsigned int; using ll = long long; #define TYPE_OF( VAR ) remove_const::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& P , vector& 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 prime{}; vector 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 curr( size ); ll div_N , div_M; vector 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; }