結果

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

ソースコード

diff # 

#include <iostream>
#include <string>
#include <stdio.h>
#include <stdint.h>
using namespace std;

using ll = long long;

#define CIN( LL , A ) LL A; cin >> A 
#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 RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT 

#include <cassert>

#define MAIN main

int MAIN()
{
  CIN( ll , N );
  constexpr const ll bound = ( ll( 1 ) << 29 ) + 1;
  assert( -bound < N && N < bound );
  CIN( int , E );
  assert( 0 <= E && E <= 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;
  }
  int kN = 0;
  // mod 5^13 = 1220703125 での1の原始4乗根123327057を前準備で計算
  ll zeta = 123327057 % five_power_E_minus_vN_half;
  while( N % 5 != 1 ){
    N = ( N * zeta ) % five_power_E_minus_vN_half;
    kN++;
  }
  if( kN % 2 == 1 ){
    RETURN( "NaN" );
  }
  N--;
  // 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
    };
  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 != 0 && 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;
  }
  kN = ( ( 4 - kN ) % 4 ) / 2;
  REPEAT( kN ){
    r = ( r * zeta ) % five_power_E_minus_vN_half;
  }
  REPEAT( vN ){
    r *= 5;
  }
  r %= five_power_E_minus_vN_half;
  if( r < bound ){
    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 ){
    RETURN( r );
  }
  RETURN( "NaN" );
}
0