結果

問題 No.2189 六平方和
ユーザー 👑 p-adicp-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 -
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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:
// 1
INT m_a;
// i
INT m_b;
// j
INT m_c;
// k
INT 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_nm_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( "" );
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0