#include #include #include #include using namespace std; 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 FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) #define QUIT return 0 #define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT #include #define MAIN main #define POWER( ANSWER , ARGUMENT , EXPONENT ) \ 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 BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \ ll ANSWER = MINIMUM; \ { \ ll VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 = 1; \ ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( MAXIMUM ) - ANSWER; \ while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 <= VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ){ \ VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 *= 2; \ } \ VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 /= 2; \ ll VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER; \ while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 != 0 ){ \ ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 + VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2; \ VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \ VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER; \ break; \ } else if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){ \ VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER; \ } \ VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 /= 2; \ } \ ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2; \ } \ \ template class Quaternion { private: // 1 INT m_a; // i INT m_b; // j INT m_c; // k INT m_d; public: inline Quaternion() noexcept; template inline Quaternion( const T& a ) noexcept; inline Quaternion( const INT& a , const INT& b , const INT& c , const INT& d ) noexcept; inline Quaternion( const Quaternion& n ) noexcept; inline const INT& GetA() const noexcept; inline const INT& GetB() const noexcept; inline const INT& GetC() const noexcept; inline const INT& GetD() const noexcept; inline Quaternion& operator+=( const Quaternion& n ) noexcept; template inline Quaternion& operator+=( const T& a ) noexcept; inline Quaternion& operator-=( const Quaternion& n ) noexcept; template inline Quaternion& operator-=( const T& a ) noexcept; inline Quaternion& operator*=( const Quaternion& n ) noexcept; template inline Quaternion& operator*=( const T& a ) noexcept; template inline Quaternion& operator/=( const T& a ) noexcept; template inline Quaternion& operator%=( const T& a ) noexcept; static inline bool Equal( const Quaternion& n0 , const Quaternion& n1 ) noexcept; }; template inline bool operator==( const Quaternion& n0 , const Quaternion& n1 ) noexcept; template inline bool operator!=( const Quaternion& n0 , const Quaternion& n1 ) noexcept; template inline Quaternion operator+( const Quaternion& n , const T& a ) noexcept; template inline Quaternion operator-( const Quaternion& n , const T& a ) noexcept; template inline Quaternion operator*( const Quaternion& n , const T& a ) noexcept; template inline Quaternion operator/( const Quaternion& n , const T& a ) noexcept; template inline Quaternion operator%( const Quaternion& n , const T& a ) noexcept; template inline Quaternion::Quaternion() noexcept : m_a() , m_b() , m_c() , m_d() {} template template inline Quaternion::Quaternion( const T& a ) noexcept : m_a( a ) , m_b() , m_c() , m_d() {} template inline Quaternion::Quaternion( const INT& a , const INT& b ,const INT& c , const INT& d ) noexcept : m_a( a ) , m_b( b ) , m_c( c ) , m_d( d ) {} template inline Quaternion::Quaternion( const Quaternion& n ) noexcept : m_a( n.m_a ) , m_b( n.m_b ) , m_c( n.m_c ) , m_d( n.m_d ) {} template inline const INT& Quaternion::GetA() const noexcept { return m_a; } template inline const INT& Quaternion::GetB() const noexcept { return m_b; } template inline const INT& Quaternion::GetC() const noexcept { return m_c; } template inline const INT& Quaternion::GetD() const noexcept { return m_d; } template inline Quaternion& Quaternion::operator+=( const Quaternion& n ) noexcept { m_a += n.m_a; m_b += n.m_b; m_c += n.m_c; m_d += n.m_d; return *this; } template template inline Quaternion& Quaternion::operator+=( const T& a ) noexcept { m_a += a; return *this; } template inline Quaternion& Quaternion::operator-=( const Quaternion& n ) noexcept { m_a -= n.m_a; m_b -= n.m_b; m_c -= n.m_c; m_d -= n.m_d; return *this; } template template inline Quaternion& Quaternion::operator-=( const T& a ) noexcept { m_a -= a; return *this; } template inline Quaternion& Quaternion::operator*=( const Quaternion& n ) noexcept { const INT a = m_a * n.m_a - m_b * n.m_b - m_c * n.m_c - m_d * n.m_d; const INT b = m_a * n.m_b + m_b * n.m_a + m_c * n.m_d - m_d * n.m_c; const INT c = m_a * n.m_c - m_b * n.m_d + m_c * n.m_a + m_d * n.m_b; m_d = m_a * n.m_d + m_b * n.m_c - m_c * n.m_b + m_d * n.m_a; m_c = c; m_b = b; m_a = a; return *this; } template template inline Quaternion& Quaternion::operator*=( const T& a ) noexcept { m_a *= a; m_b *= a; m_c *= a; m_d *= a; return *this; } template template inline Quaternion& Quaternion::operator/=( const T& a ) noexcept { m_a /= a; m_b /= a; m_c /= a; m_d /= a; return *this; } template template inline Quaternion& Quaternion::operator%=( const T& a ) noexcept { m_a %= a; m_b %= a; m_c %= a; m_d %= a; return *this; } template inline bool Quaternion::Equal( const Quaternion& n0 , const Quaternion& n1 ) noexcept { return n0.m_a == n1.m_a && n0.m_b == n1.m_b && n0.m_c == n1.m_c && n0.m_d == n1.m_d; } template inline bool operator==( const Quaternion& n0 , const Quaternion& n1 ) noexcept { return Quaternion::Equal( n0 , n1 ); } template inline bool operator!=( const Quaternion& n0 , const Quaternion& n1 ) noexcept { return ! Quaternion::Equal( n0 , n1 ); } template inline Quaternion operator+( const Quaternion& n , const T& a ) noexcept { return Quaternion( n ).operator+=( a ); } template inline Quaternion operator-( const Quaternion& n , const T& a ) noexcept { return Quaternion( n ).operator-=( a ); } template inline Quaternion operator*( const Quaternion& n , const T& a ) noexcept { return Quaternion( n ).operator*=( a ); } template inline Quaternion operator/( const Quaternion& n , const T& a ) noexcept { return Quaternion( n ).operator/=( a ); } template inline Quaternion operator%( const Quaternion& n , const T& a ) noexcept { return Quaternion( n ).operator%=( a ); } template class QuotientRing { protected: INT m_n; const INT* m_p_M; public: inline QuotientRing() noexcept; inline QuotientRing( const INT& n , const INT* const & p_M = nullptr ) noexcept; inline QuotientRing( const QuotientRing& n ) noexcept; inline QuotientRing& operator+=( const QuotientRing& n ) noexcept; inline QuotientRing& operator+=( const INT& n ) noexcept; // operator<が定義されていても負の数は正に直さず剰余を取ることに注意。 inline QuotientRing& operator-=( const QuotientRing& n ) noexcept; inline QuotientRing& operator-=( const INT& n ) noexcept; inline QuotientRing& operator*=( const QuotientRing& n ) noexcept; inline QuotientRing& operator*=( const INT& n ) noexcept; inline const INT& Represent() const noexcept; inline const INT& GetModulo() const noexcept; // m_nの正負やm_p_Mの一致込みの等号。 static inline bool Equal( const QuotientRing& n0 , const QuotientRing& n1 ) noexcept; template static QuotientRing Power( const QuotientRing& n , const T& exponent ); }; template inline bool operator==( const QuotientRing& n0 , const QuotientRing& n1 ) noexcept; template inline bool operator!=( const QuotientRing& n0 , const QuotientRing& n1 ) noexcept; template inline QuotientRing operator+( const QuotientRing& n0 , const T& n1 ) noexcept; template inline QuotientRing operator-( const QuotientRing& n0 , const T& n1 ) noexcept; template inline QuotientRing operator*( const QuotientRing& n0 , const T& n1 ) noexcept; template inline QuotientRing Power( const QuotientRing& n , const T& exponent ); template inline QuotientRing::QuotientRing() noexcept : m_n() , m_p_M( nullptr ) {} template inline QuotientRing::QuotientRing( const INT& n , const INT* const & p_M ) noexcept : m_n( p_M == nullptr ? n : n % *p_M ) , m_p_M( p_M ) {} template inline QuotientRing::QuotientRing( const QuotientRing& n ) noexcept : m_n( n.m_n ) , m_p_M( n.m_p_M ) {} template inline QuotientRing& QuotientRing::operator+=( const QuotientRing& n ) noexcept { if( m_p_M == nullptr ){ m_p_M = n.m_p_M; } m_n += n.m_n; if( m_p_M != nullptr ){ m_n %= *m_p_M; } return *this; } template inline QuotientRing& QuotientRing::operator+=( const INT& n ) noexcept { m_n += n; if( m_p_M != nullptr ){ m_n %= *m_p_M; } return *this; } template inline QuotientRing& QuotientRing::operator-=( const QuotientRing& n ) noexcept { if( m_p_M == nullptr ){ m_p_M = n.m_p_M; } m_n -= n.m_n; if( m_p_M != nullptr ){ m_n %= *m_p_M; } return *this; } template inline QuotientRing& QuotientRing::operator-=( const INT& n ) noexcept { m_n -= n; if( m_p_M != nullptr ){ m_n %= *m_p_M; } return *this; } template inline QuotientRing& QuotientRing::operator*=( const QuotientRing& n ) noexcept { if( m_p_M == nullptr ){ m_p_M = n.m_p_M; } m_n *= n.m_n; if( m_p_M != nullptr ){ m_n %= *m_p_M; } return *this; } template inline QuotientRing& QuotientRing::operator*=( const INT& n ) noexcept { m_n *= n; if( m_p_M != nullptr ){ m_n %= *m_p_M; } return *this; } template inline const INT& QuotientRing::Represent() const noexcept { return m_n; } template inline const INT& QuotientRing::GetModulo() const noexcept { static const INT zero{ 0 }; return m_p_M == nullptr ? zero : *m_p_M; } template inline bool QuotientRing::Equal( const QuotientRing& n0 , const QuotientRing& n1 ) noexcept { return n0.m_n == n1.m_n && n0.m_p_M == n1.m_p_M; } template template QuotientRing QuotientRing::Power( const QuotientRing& n , const T& exponent ) { QuotientRing answer{ 1 , n.m_p_M }; QuotientRing power{ n }; while( exponent != 0 ){ if( exponent % 2 == 1 ){ answer *= power; } power *= power; exponent /= 2; } return answer; } template inline bool operator==( const QuotientRing& n0 , const QuotientRing& n1 ) noexcept { return QuotientRing::Equal( n0 , n1 ); } template inline bool operator!=( const QuotientRing& n0 , const QuotientRing& n1 ) noexcept { return ! QuotientRing::Equal( n0 , n1 ); } template inline QuotientRing operator+( const QuotientRing& n0 , const T& n1 ) noexcept { return QuotientRing( n0 ).operator+=( n1 ); } template inline QuotientRing operator-( const QuotientRing& n0 , const T& n1 ) noexcept { return QuotientRing( n0 ).operator-=( n1 ); } template inline QuotientRing operator*( const QuotientRing& n0 , const T& n1 ) noexcept { return QuotientRing( n0 ).operator*=( n1 ); } template inline QuotientRing Power( const QuotientRing& n , const T& exponent ) { return QuotientRing::template Power( n , exponent ); } int MAIN() { UNTIE; CEXPR( ll , bound_N , 1000000000000000000 ); CIN_ASSERT( N , 1 , bound_N ); CEXPR( ll , bound_M , 1000 ); CIN_ASSERT( M , 1 , bound_M ); CEXPR( ll , bound_B , 1000000000 ); CIN_ASSERT( B , 1 , bound_B ); BS2( sqrtM , 1 , M , sqrtM * sqrtM , M ); ll a , b , c , d; ll x02 , x12; ll diff0 , diff1 , diff2; bool found = false; FOREQ( x0 , 0 , sqrtM ){ x02 = x0 * x0; diff0 = M - x02; FOREQ( x1 , 0 , sqrtM ){ x12 = x1 * x1; diff1 = diff0 - x12; if( diff1 < 0 ){ break; } FOREQ( x2 , 0 , sqrtM ){ diff2 = diff1 - x2 * x2; if( diff2 < 0 ){ break; } BS2( x3 , 0 , diff2 , x3 * x3 , diff2 ); if( x3 * x3 == diff2 ){ a = x0; b = x1; c = x2; d = x3; found = true; break; } } if( found ){ break; } } if( found ){ break; } } assert( found ); Quaternion > z{ QuotientRing( a , &B ) , QuotientRing( b , &B ) , QuotientRing( c , &B ) , QuotientRing( d , &B ) }; POWER( power_z , z , N ); a = power_z.GetA().Represent(); b = power_z.GetB().Represent(); c = power_z.GetC().Represent(); d = power_z.GetD().Represent(); if( a <= 0 ){ a += B; } if( b <= 0 ){ b += B; } if( c <= 0 ){ c += B; } if( d <= 0 ){ d += B; } cout << "Yes\n"; cout << a << " " << b << " " << c << " " << d << " " << B << " " << B; RETURN( "" ); }