結果
問題 | No.2891 Mint |
ユーザー |
|
提出日時 | 2024-12-16 10:49:06 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,775 ms / 2,000 ms |
コード長 | 1,424 bytes |
コンパイル時間 | 3,443 ms |
コンパイル使用メモリ | 267,564 KB |
実行使用メモリ | 26,716 KB |
最終ジャッジ日時 | 2024-12-16 10:49:40 |
合計ジャッジ時間 | 28,523 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 54 |
ソースコード
#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #ifndef LOCAL #include <bits/stdc++.h> using namespace std; #define debug(...) (void(0)) #else #include "algo/debug.h" #endif #include <atcoder/modint> using mint = atcoder::modint998244353; mint arith(mint a0, mint d, mint len) { return (a0 * 2 + (len - 1) * d) * len / 2; } void solve() { int64_t N, M; cin >> N >> M; vector<int64_t> thr; vector<mint> sum{0}; for (int64_t i = 1; i < N;) { int64_t lo = i, hi = N; while (hi > lo + 1) { int64_t mi = (lo + hi) / 2; (M / mi == M / i ? lo : hi) = mi; } thr.push_back(i); sum.push_back(sum.back() + arith(M % i, -M / i, lo - i + 1)); if (i == hi) break; i = hi; } const auto g = [&](int64_t r) -> mint { if (r <= 0) return 0; int64_t hi = r, lo = 0; while (hi > lo + 1) { int64_t mi = (hi + lo) / 2; (M / mi == M / r ? hi : lo) = mi; } int64_t k = distance(thr.begin(), lower_bound(thr.begin(), thr.end(), hi)); mint ans = sum[k]; ans += arith(M % hi, -M / hi, r - hi + 1); return ans; }; mint ans = g(N); cout << ans.val() << '\n'; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int tt = 1; // std::cin >> tt; while (tt--) { solve(); } }