結果
問題 |
No.2440 Accuracy of Integer Division Approximate Functions
|
ユーザー |
👑 |
提出日時 | 2023-09-02 19:58:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 45 ms / 2,000 ms |
コード長 | 1,023 bytes |
コンパイル時間 | 5,129 ms |
コンパイル使用メモリ | 313,264 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-12 02:20:49 |
合計ジャッジ時間 | 7,287 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
#include <cassert> // assert #include <iostream> // cin, cout, ios #include <utility> // swap #include <boost/multiprecision/cpp_int.hpp> namespace mp = boost::multiprecision; using bigint = mp::cpp_int; bigint floor_sum(bigint n, bigint m, bigint a, bigint b) { assert(n >= 0 && m > 0 && a >= 0 && b >= 0); bigint x = 0, q; while(n > 0) { mp::divide_qr(a, m, q, a); x += q * (n * (n - 1) >> 1); mp::divide_qr(b, m, q, b); x += q * n; mp::divide_qr(a * n + b, m, n, b); std::swap(a, m); } return x; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); int q, s; bigint n, d, m, t, u; std::cin >> q; for(int i = 0; i < q; i++) { std::cin >> n >> d >> m >> s; t = (bigint)1 << s, u = d * m; if (t != u) { n = mp::min(n, d * t / mp::abs(t - u)); n -= mp::abs(floor_sum(n + 1, t, m, 0) - floor_sum(n + 1, d, 1, 0)); } std::cout << n << '\n'; } }