結果
問題 |
No.8072 Sum of sqrt(x)
|
ユーザー |
|
提出日時 | 2021-10-25 22:50:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,146 bytes |
コンパイル時間 | 9,233 ms |
コンパイル使用メモリ | 360,300 KB |
最終ジャッジ日時 | 2025-01-25 06:51:00 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 4 TLE * 22 OLE * 1 |
ソースコード
#include <iostream> #include <iomanip> #include <boost/multiprecision/cpp_int.hpp> using namespace std; using namespace boost::multiprecision; typedef cpp_int Bint; typedef long long int llint; typedef long double real_t; 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() { Bint unit = pow(Bint(10),20); cout << fixed << setprecision(17); 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 << real_t(ans)/real_t(unit) << endl; } return 0; }