結果

問題 No.2271 平方根の１３桁精度近似計算
コンテスト
ユーザー 👑 p-adic
提出日時 2023-04-09 15:12:15
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,152 bytes
コンパイル時間 950 ms
コンパイル使用メモリ 78,300 KB
最終ジャッジ日時 2025-02-12 04:13:19
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ( "O3" )
#pragma GCC optimize( "unroll-loops" )
#pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
#include <iostream>
#include <stdio.h>
#include <stdint.h>
#include <cassert>
#include <string>
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 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( remove_const<remove_reference<decltype( FINAL_PLUS_ONE )>::type >::type VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) 
#define QUIT return 0
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT 

#define MAIN main

int MAIN()
{
  UNTIE;
  CEXPR( ll , bound_N , ( ll( 1 ) << 29 ) + 1 );
  CIN_ASSERT( N , -bound_N , bound_N );
  CEXPR( int , bound_E , 13 );
  CIN_ASSERT( E , 0 , 13 );
  if( N == 0 ){
    RETURN( 0 );
  } else if( N < 0 ){
    N += 1220703125;
  }
  int vN = 0;
  while( N % 5 == 0 ){
    N /= 5;
    vN++;
  }
  if( vN >= E ){
    RETURN( 0 );
  } else if( vN % 2 == 1 ){
    RETURN( "NaN" );
  }
  vN /= 2;
  int E_minus_vN_half = E - vN;
  ll five_power_E_minus_vN_half = 1;
  REPEAT( E_minus_vN_half ){
    five_power_E_minus_vN_half *= 5;
  }
  ll N_r = N % 5;
  if( N_r == 2 || N_r == 3 ){
    RETURN( "NaN" );
  }
  // mod 5^13 = 1220703125 での5素成分の逆元を前準備で計算
  constexpr const ll inverse[18] =
    {
      0 , // ダミー
      1 ,
      610351563 ,
      406901042 ,
      915527344 ,
      1 ,
      203450521 ,
      697544643 ,
      457763672 ,
      949435764 ,
      610351563 ,
      887784091 ,
      712076823 ,
      469501202 ,
      959123884 ,
      406901042 ,
      228881836 ,
      789866728
    };
  N = ( ( N * inverse[N_r] ) - 1 ) % five_power_E_minus_vN_half;
  const ll& half = inverse[2];
  ll r = 1;
  ll uN_minus_power = 1;
  ll product = 1;
  ll factorial = 1;
  ll five_power_i = 1;
  ll term;
  FOR( i , 1 , 18 ){
    uN_minus_power = ( uN_minus_power * N ) % five_power_E_minus_vN_half;
    product = ( product * ( half + 1 - i ) ) % five_power_E_minus_vN_half;
    factorial = ( factorial * inverse[i] ) % five_power_E_minus_vN_half;
    if( i % 5 == 0 ){
      five_power_i *= 5;
    }
    term = ( product * factorial ) % five_power_E_minus_vN_half;
    term = ( term * ( uN_minus_power / five_power_i ) ) % five_power_E_minus_vN_half;
    r = ( r + term ) % five_power_E_minus_vN_half;
  }
  r *= ( N_r == 1 ? 1 : 2 );
  REPEAT( vN ){
    r *= 5;
  }
  r %= five_power_E_minus_vN_half;
  if( r < bound_N ){
    RETURN( r );
  }
  ll five_power_E = five_power_E_minus_vN_half;
  REPEAT( vN ){
    five_power_E *= 5;
  }
  r = five_power_E - r;
  if( r < bound_N ){
    RETURN( r );
  }
  RETURN( "NaN" );
}
0