#829585 (C++17) No.2189 六平方和

提出ソース
結果

問題	No.2189 六平方和
ユーザー	👑 p-adic
提出日時	2022-12-31 19:49:53
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	15,563 bytes
コンパイル時間	641 ms
コンパイル使用メモリ	72,256 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-05-05 02:24:46
合計ジャッジ時間	1,657 ms
ジャッジサーバーID （参考情報）	judge5 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	1 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	1 ms 5,376 KB
testcase_10	AC	2 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	2 ms 5,376 KB
testcase_16	AC	1 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	1 ms 5,376 KB
testcase_19	AC	1 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	1 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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_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( "" );
}
yukicoder

結果

テストケース

ソースコード
