結果

問題 No.2940 Sigma Sigma Div Floor Problem
コンテスト
ユーザー mkawa2
提出日時 2024-10-18 22:59:08
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,493 bytes
コンパイル時間 1,000 ms
コンパイル使用メモリ 101,384 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-10-18 22:59:20
合計ジャッジ時間 2,003 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 3
other AC * 1 WA * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cmath>

const int md = 998244353;

int floor_sqrt(int x) {
    int a = round(sqrt(x) - 0.49);
    while (a * a > x) a--;
    return a;
}

long long floor_sum(long long n, long long m, long long a, long long b) {
    long long ans = 0;
    if (a < 0) {
        ans += n * (n - 1) / 2 * (a / m);
        a %= m;
    }
    if (b < 0) {
        ans += n * (b / m);
        b %= m;
    }
    while (true) {
        if (a >= m) {
            ans += n * (n - 1) / 2 * (a / m);
            a %= m;
        }
        if (b >= m) {
            ans += n * (b / m);
            b %= m;
        }
        long long y_max = a * n + b;
        if (y_max < m) break;
        long long new_n = y_max / m;
        long long new_b = y_max % m;
        long long new_m = a;
        long long new_a = m;
        n = new_n;
        b = new_b;
        m = new_m;
        a = new_a;
    }
    return ans;
}

int main() {
    int n;
    std::cin >> n;
    long long ans = 0;
    int m = n + 1;

    int root = floor_sqrt(n);
    long long s = (long long)n * (n + 1) / 2;
    for (int d = 1; d <= root; d++) {
        long long t = s;
        s = floor_sum(n + 1, d + 1, 1, 0);
        ans += (long long)d * (t - s);
        ans %= md;
    }
    for (int d = 1; d <= n / root; d++) {
        int q = m / d;
        int r = m % d;
        ans += (long long)(root + q) * (q - root - 1) / 2 * d + (long long)r * q;
        ans %= md;
    }
    std::cout << ans << std::endl;
    return 0;
}
0