Submission #67545192

Source Code Expand

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const long long MOD = 998244353;

int main() {
    long long N;
    cin >> N;
    if (N < 3) {
        cout << 0 << endl;
        return 0;
    }
    long long ans = 0;
    long long K = static_cast<long long>(sqrt(N));

    for (long long b = 2; b <= K; b++) {
        long long q = N / b;
        long long r = N % b;
        long long term1 = (b - 1) * q;
        long long term2 = 0;
        if (b - 1 > r) {
            term2 = b - 1 - r;
        }
        ans = (ans + term1 - term2) % MOD;
    }

    for (long long q_val = 1; q_val <= K; q_val++) {
        long long L = N / (q_val + 1) + 1;
        long long R = N / q_val;
        if (L > R) continue;
        L = max(L, K + 1);
        if (L > R) continue;

        __int128 n_terms = static_cast<__int128>(R - L + 1);
        __int128 first_term = static_cast<__int128>(L - 1);
        __int128 last_term = static_cast<__int128>(R - 1);
        __int128 sum1 = (first_term + last_term) * n_terms / 2;
        sum1 = static_cast<__int128>(q_val) * sum1;

        long long b0 = (N + 1 + q_val) / (q_val + 1);
        b0 = max(b0, L);
        __int128 sum2 = 0;
        if (b0 <= R) {
            __int128 n_terms2 = static_cast<__int128>(R - b0 + 1);
            __int128 first_b = static_cast<__int128>(b0);
            __int128 last_b = static_cast<__int128>(R);
            __int128 sum_b = (first_b + last_b) * n_terms2 / 2;
            __int128 part1 = static_cast<__int128>(q_val + 1) * sum_b;
            __int128 part2 = static_cast<__int128>(N + 1) * n_terms2;
            sum2 = part1 - part2;
        }

        __int128 total_interval = sum1 - sum2;
        long long add = static_cast<long long>(total_interval % MOD);
        ans = (ans + add) % MOD;
    }

    ans = (ans % MOD + MOD) % MOD;
    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Count A%B=C
User yangyang1000
Language C++ 20 (gcc 12.2)
Score 475
Code Size 1952 Byte
Status AC
Exec Time 20 ms
Memory 3680 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 475 / 475
Status
AC × 3
AC × 56
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt
All 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt, 01-43.txt, 01-44.txt, 01-45.txt, 01-46.txt, 01-47.txt, 01-48.txt, 01-49.txt, 01-50.txt, 01-51.txt, 01-52.txt, 01-53.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 1 ms 3432 KiB
00-sample-02.txt AC 1 ms 3504 KiB
00-sample-03.txt AC 14 ms 3476 KiB
01-01.txt AC 1 ms 3408 KiB
01-02.txt AC 1 ms 3680 KiB
01-03.txt AC 1 ms 3476 KiB
01-04.txt AC 1 ms 3536 KiB
01-05.txt AC 1 ms 3612 KiB
01-06.txt AC 1 ms 3408 KiB
01-07.txt AC 1 ms 3504 KiB
01-08.txt AC 1 ms 3540 KiB
01-09.txt AC 1 ms 3504 KiB
01-10.txt AC 1 ms 3548 KiB
01-11.txt AC 1 ms 3552 KiB
01-12.txt AC 1 ms 3432 KiB
01-13.txt AC 1 ms 3472 KiB
01-14.txt AC 1 ms 3676 KiB
01-15.txt AC 20 ms 3612 KiB
01-16.txt AC 20 ms 3556 KiB
01-17.txt AC 20 ms 3436 KiB
01-18.txt AC 20 ms 3472 KiB
01-19.txt AC 20 ms 3532 KiB
01-20.txt AC 20 ms 3528 KiB
01-21.txt AC 19 ms 3504 KiB
01-22.txt AC 19 ms 3408 KiB
01-23.txt AC 19 ms 3504 KiB
01-24.txt AC 20 ms 3412 KiB
01-25.txt AC 20 ms 3560 KiB
01-26.txt AC 20 ms 3552 KiB
01-27.txt AC 19 ms 3612 KiB
01-28.txt AC 1 ms 3480 KiB
01-29.txt AC 1 ms 3604 KiB
01-30.txt AC 1 ms 3508 KiB
01-31.txt AC 1 ms 3472 KiB
01-32.txt AC 1 ms 3472 KiB
01-33.txt AC 1 ms 3604 KiB
01-34.txt AC 1 ms 3436 KiB
01-35.txt AC 1 ms 3468 KiB
01-36.txt AC 2 ms 3552 KiB
01-37.txt AC 1 ms 3552 KiB
01-38.txt AC 2 ms 3472 KiB
01-39.txt AC 2 ms 3412 KiB
01-40.txt AC 2 ms 3440 KiB
01-41.txt AC 2 ms 3556 KiB
01-42.txt AC 14 ms 3436 KiB
01-43.txt AC 16 ms 3548 KiB
01-44.txt AC 4 ms 3500 KiB
01-45.txt AC 19 ms 3468 KiB
01-46.txt AC 7 ms 3508 KiB
01-47.txt AC 1 ms 3608 KiB
01-48.txt AC 9 ms 3532 KiB
01-49.txt AC 4 ms 3552 KiB
01-50.txt AC 12 ms 3440 KiB
01-51.txt AC 14 ms 3616 KiB
01-52.txt AC 3 ms 3472 KiB
01-53.txt AC 17 ms 3552 KiB