結果
問題 |
No.8072 Sum of sqrt(x)
|
ユーザー |
|
提出日時 | 2021-10-25 23:01:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,236 bytes |
コンパイル時間 | 4,654 ms |
コンパイル使用メモリ | 364,780 KB |
最終ジャッジ日時 | 2025-01-25 06:52:42 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 4 TLE * 22 OLE * 1 |
ソースコード
#include <iostream> #include <ios> #include <iomanip> #include <boost/multiprecision/cpp_int.hpp> using namespace std; using namespace boost::multiprecision; typedef cpp_int Bint; Bint sqrt_floor(Bint x) { Bint ceil = x, floor = 1; while (ceil > floor + 1) { auto m = (ceil+floor)/2; if (m*m <= x) floor = m; else ceil = m; } return floor; } int main() { const int prec = 20; Bint unit = pow(Bint(10),prec); int N; cin >> N; Bint ans = 0; for (auto i=0; i<N; ++i) { Bint x; cin >> x; auto p = sqrt_floor(x); if (p*p == x) { ans += p*unit; } else { Bint R = 1; Bint U = 1, V = p; Bint a = 2*p, b = x-p*p; while (R < unit) { R *= 2*p; auto prev_V = V; V = a*V + b*U; U = prev_V; } ans -= p * unit; ans += (V * unit)/U; } cout << ans / unit << "." << setfill('0') << right << setw(prec - 3) << (ans % unit)/1000 << std::setfill(' ') << endl; } return 0; }