結果

問題 No.2940 Sigma Sigma Div Floor Problem
ユーザー mkawa2mkawa2
提出日時 2024-10-18 22:59:08
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 1 ms
6,820 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 1 ms
6,820 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
08_evil_01.txt WA -
権限があれば一括ダウンロードができます

ソースコード

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