#815098 (C++17(gcc12)) No.2271 平方根の１３桁精度近似計算

• 問題: No.2271 平方根の１３桁精度近似計算
• ユーザー: 👑 p-adic
• 提出日時: 2022-11-08 13:03:27
• 言語: C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 2,619 bytes
• コンパイル時間: 677 ms
• コンパイル使用メモリ: 67,900 KB
• 最終ジャッジ日時: 2025-02-08 19:11:57
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
other	AC * 40

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#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;
  }
  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 != 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;
  }
  r *= ( N_r == 1 ? 1 : 2 );
  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" );
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX