結果

問題 No.2891 Mint
ユーザー ooaiu
提出日時 2024-12-16 11:02:01
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 128 ms / 2,000 ms
コード長 1,026 bytes
コンパイル時間 3,164 ms
コンパイル使用メモリ 250,696 KB
実行使用メモリ 54,232 KB
最終ジャッジ日時 2024-12-16 11:02:10
合計ジャッジ時間 7,496 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 54
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef LOCAL
#include <bits/stdc++.h>

using namespace std;

#define debug(...) (void(0))
#else
#include "algo/debug.h"
#endif

vector<array<int64_t, 3>> Quotients(int64_t N) {
    vector<array<int64_t, 3>> res;
    int64_t l = 1;
    while(l <= N) {
        int64_t p = N / l;
        int64_t r = N / p + 1;
        res.push_back({p, l, r});
        l = r;
    }
    return res;
}

#include <atcoder/modint>
using mint = atcoder::modint998244353;
const mint inv2 = mint(2).inv();
mint arith(mint a0, mint d, mint len) { return (a0 * 2 + (len - 1) * d) * len * inv2; }

void solve() {
    int64_t N, M;
    cin >> N >> M;
    auto qq = Quotients(M);
    qq.push_back({0, qq.back()[2], N + 1});
    mint ans = 0;
    for(const auto&[p, l, r]: qq) {
        ans += arith(M % l, -p, min(N + 1, r) - l);
        if(N < r) break;
    }
    cout << ans.val() << endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int tt = 1;
    // std::cin >> tt;
    while (tt--) {
        solve();
    }
}
0