結果
問題 | No.2189 六平方和 |
ユーザー | 👑 p-adic |
提出日時 | 2022-11-13 16:31:29 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 15,563 bytes |
コンパイル時間 | 772 ms |
コンパイル使用メモリ | 73,276 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-26 19:17:05 |
合計ジャッジ時間 | 5,314 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
ソースコード
#include <iostream>#include <string>#include <stdio.h>#include <stdint.h>using namespace std;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 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 <cassert>#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 <typename INT>class Quaternion{private:// 1INT m_a;// iINT m_b;// jINT m_c;// kINT m_d;public:inline Quaternion() noexcept;template <typename T> 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<INT>& 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<INT>& operator+=( const Quaternion<INT>& n ) noexcept;template <typename T> inline Quaternion<INT>& operator+=( const T& a ) noexcept;inline Quaternion<INT>& operator-=( const Quaternion<INT>& n ) noexcept;template <typename T> inline Quaternion<INT>& operator-=( const T& a ) noexcept;inline Quaternion<INT>& operator*=( const Quaternion<INT>& n ) noexcept;template <typename T> inline Quaternion<INT>& operator*=( const T& a ) noexcept;template <typename T> inline Quaternion<INT>& operator/=( const T& a ) noexcept;template <typename T> inline Quaternion<INT>& operator%=( const T& a ) noexcept;static inline bool Equal( const Quaternion<INT>& n0 , const Quaternion<INT>& n1 ) noexcept;};template <typename INT> inline bool operator==( const Quaternion<INT>& n0 , const Quaternion<INT>& n1 ) noexcept;template <typename INT> inline bool operator!=( const Quaternion<INT>& n0 , const Quaternion<INT>& n1 ) noexcept;template <typename INT , typename T> inline Quaternion<INT> operator+( const Quaternion<INT>& n , const T& a ) noexcept;template <typename INT , typename T> inline Quaternion<INT> operator-( const Quaternion<INT>& n , const T& a ) noexcept;template <typename INT , typename T> inline Quaternion<INT> operator*( const Quaternion<INT>& n , const T& a ) noexcept;template <typename INT , typename T> inline Quaternion<INT> operator/( const Quaternion<INT>& n , const T& a ) noexcept;template <typename INT , typename T> inline Quaternion<INT> operator%( const Quaternion<INT>& n , const T& a ) noexcept;template <typename INT> inline Quaternion<INT>::Quaternion() noexcept : m_a() , m_b() , m_c() , m_d() {}template <typename INT> template <typename T> inline Quaternion<INT>::Quaternion( const T& a ) noexcept : m_a( a ) , m_b() , m_c() , m_d() {}template <typename INT> inline Quaternion<INT>::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 <typename INT> inline Quaternion<INT>::Quaternion( const Quaternion<INT>& n ) noexcept : m_a( n.m_a ) , m_b( n.m_b ) , m_c( n.m_c ) , m_d( n.m_d ) {}template <typename INT> inline const INT& Quaternion<INT>::GetA() const noexcept { return m_a; }template <typename INT> inline const INT& Quaternion<INT>::GetB() const noexcept { return m_b; }template <typename INT> inline const INT& Quaternion<INT>::GetC() const noexcept { return m_c; }template <typename INT> inline const INT& Quaternion<INT>::GetD() const noexcept { return m_d; }template <typename INT> inline Quaternion<INT>& Quaternion<INT>::operator+=( const Quaternion<INT>& 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 <typename INT> template <typename T> inline Quaternion<INT>& Quaternion<INT>::operator+=( const T& a ) noexcept { m_a += a; return *this; }template <typename INT> inline Quaternion<INT>& Quaternion<INT>::operator-=( const Quaternion<INT>& 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 <typename INT> template <typename T> inline Quaternion<INT>& Quaternion<INT>::operator-=( const T& a ) noexcept { m_a -= a; return *this; }template <typename INT> inline Quaternion<INT>& Quaternion<INT>::operator*=( const Quaternion<INT>& 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 <typename INT> template <typename T> inline Quaternion<INT>& Quaternion<INT>::operator*=( const T& a ) noexcept { m_a *= a; m_b *= a; m_c *=a; m_d *= a; return *this; }template <typename INT> template <typename T> inline Quaternion<INT>& Quaternion<INT>::operator/=( const T& a ) noexcept { m_a /= a; m_b /= a; m_c /=a; m_d /= a; return *this; }template <typename INT> template <typename T> inline Quaternion<INT>& Quaternion<INT>::operator%=( const T& a ) noexcept { m_a %= a; m_b %= a; m_c %=a; m_d %= a; return *this; }template <typename INT> inline bool Quaternion<INT>::Equal( const Quaternion<INT>& n0 , const Quaternion<INT>& 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 <typename INT> inline bool operator==( const Quaternion<INT>& n0 , const Quaternion<INT>& n1 ) noexcept { return Quaternion<INT>::Equal( n0, n1 ); }template <typename INT> inline bool operator!=( const Quaternion<INT>& n0 , const Quaternion<INT>& n1 ) noexcept { return ! Quaternion<INT>::Equal(n0 , n1 ); }template <typename INT , typename T> inline Quaternion<INT> operator+( const Quaternion<INT>& n , const T& a ) noexcept { return Quaternion<INT>( n).operator+=( a ); }template <typename INT , typename T> inline Quaternion<INT> operator-( const Quaternion<INT>& n , const T& a ) noexcept { return Quaternion<INT>( n).operator-=( a ); }template <typename INT , typename T> inline Quaternion<INT> operator*( const Quaternion<INT>& n , const T& a ) noexcept { return Quaternion<INT>( n).operator*=( a ); }template <typename INT , typename T> inline Quaternion<INT> operator/( const Quaternion<INT>& n , const T& a ) noexcept { return Quaternion<INT>( n).operator/=( a ); }template <typename INT , typename T> inline Quaternion<INT> operator%( const Quaternion<INT>& n , const T& a ) noexcept { return Quaternion<INT>( n).operator%=( a ); }template <typename INT>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<INT>& n ) noexcept;inline QuotientRing<INT>& operator+=( const QuotientRing<INT>& n ) noexcept;inline QuotientRing<INT>& operator+=( const INT& n ) noexcept;// operator<が定義されていても負の数は正に直さず剰余を取ることに注意。inline QuotientRing<INT>& operator-=( const QuotientRing<INT>& n ) noexcept;inline QuotientRing<INT>& operator-=( const INT& n ) noexcept;inline QuotientRing<INT>& operator*=( const QuotientRing<INT>& n ) noexcept;inline QuotientRing<INT>& 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<INT>& n0 , const QuotientRing<INT>& n1 ) noexcept;template <typename T> static QuotientRing<INT> Power( const QuotientRing<INT>& n , const T& exponent );};template <typename INT> inline bool operator==( const QuotientRing<INT>& n0 , const QuotientRing<INT>& n1 ) noexcept;template <typename INT> inline bool operator!=( const QuotientRing<INT>& n0 , const QuotientRing<INT>& n1 ) noexcept;template <typename INT , typename T> inline QuotientRing<INT> operator+( const QuotientRing<INT>& n0 , const T& n1 ) noexcept;template <typename INT , typename T> inline QuotientRing<INT> operator-( const QuotientRing<INT>& n0 , const T& n1 ) noexcept;template <typename INT , typename T> inline QuotientRing<INT> operator*( const QuotientRing<INT>& n0 , const T& n1 ) noexcept;template <typename INT , typename T> inline QuotientRing<INT> Power( const QuotientRing<INT>& n , const T& exponent );template <typename INT> inline QuotientRing<INT>::QuotientRing() noexcept : m_n() , m_p_M( nullptr ) {}template <typename INT> inline QuotientRing<INT>::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 <typename INT> inline QuotientRing<INT>::QuotientRing( const QuotientRing<INT>& n ) noexcept : m_n( n.m_n ) , m_p_M( n.m_p_M ) {}template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator+=( const QuotientRing<INT>& 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 <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator+=( const INT& n ) noexcept { m_n += n; if( m_p_M != nullptr ){ m_n %=*m_p_M; } return *this; }template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator-=( const QuotientRing<INT>& 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 <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator-=( const INT& n ) noexcept { m_n -= n; if( m_p_M != nullptr ){ m_n %=*m_p_M; } return *this; }template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator*=( const QuotientRing<INT>& 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 <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator*=( const INT& n ) noexcept { m_n *= n; if( m_p_M != nullptr ){ m_n %=*m_p_M; } return *this; }template <typename INT> inline const INT& QuotientRing<INT>::Represent() const noexcept { return m_n; }template <typename INT> inline const INT& QuotientRing<INT>::GetModulo() const noexcept { static const INT zero{ 0 }; return m_p_M == nullptr ? zero: *m_p_M; }template <typename INT> inline bool QuotientRing<INT>::Equal( const QuotientRing<INT>& n0 , const QuotientRing<INT>& n1 ) noexcept { return n0.m_n ==n1.m_n && n0.m_p_M == n1.m_p_M; }template <typename INT> template <typename T>QuotientRing<INT> QuotientRing<INT>::Power( const QuotientRing<INT>& n , const T& exponent ){QuotientRing<INT> answer{ 1 , n.m_p_M };QuotientRing<INT> power{ n };while( exponent != 0 ){if( exponent % 2 == 1 ){answer *= power;}power *= power;exponent /= 2;}return answer;}template <typename INT> inline bool operator==( const QuotientRing<INT>& n0 , const QuotientRing<INT>& n1 ) noexcept { return QuotientRing<INT>::Equal( n0 , n1 ); }template <typename INT> inline bool operator!=( const QuotientRing<INT>& n0 , const QuotientRing<INT>& n1 ) noexcept { return ! QuotientRing<INT>::Equal( n0 , n1 ); }template <typename INT , typename T> inline QuotientRing<INT> operator+( const QuotientRing<INT>& n0 , const T& n1 ) noexcept { return QuotientRing<INT>( n0 ).operator+=( n1 ); }template <typename INT , typename T> inline QuotientRing<INT> operator-( const QuotientRing<INT>& n0 , const T& n1 ) noexcept { return QuotientRing<INT>( n0 ).operator-=( n1 ); }template <typename INT , typename T> inline QuotientRing<INT> operator*( const QuotientRing<INT>& n0 , const T& n1 ) noexcept { return QuotientRing<INT>( n0 ).operator*=( n1 ); }template <typename INT , typename T> inline QuotientRing<INT> Power( const QuotientRing<INT>& n , const T& exponent ) { return QuotientRing<INT>::template Power<T>( 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<QuotientRing<ll> > z{ QuotientRing<ll>( a , &B ) , QuotientRing<ll>( b , &B ) , QuotientRing<ll>( c , &B ) , QuotientRing<ll>( 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( "" );}