結果

問題 No.752 mod数列
ユーザー PachicobuePachicobue
提出日時 2018-11-09 22:18:20
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,925 bytes
コンパイル時間 2,858 ms
コンパイル使用メモリ 204,340 KB
実行使用メモリ 5,852 KB
最終ジャッジ日時 2023-08-13 11:40:11
合計ジャッジ時間 7,882 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 4 ms
4,384 KB
testcase_04 AC 3 ms
4,384 KB
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 AC 172 ms
4,384 KB
testcase_16 AC 191 ms
5,696 KB
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 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 3 ms
4,380 KB
testcase_32 AC 4 ms
4,380 KB
testcase_33 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

//=================================
// Created on: 2018/11/09 21:30:39
//=================================
#include <bits/stdc++.h>
using ll = __int128_t;
int main()
{
    long long P;
    int Q;
    std::cin >> P >> Q;
    constexpr ll SQRT = 32000;
    std::vector<ll> f(SQRT + 1, 0);
    for (ll i = 1; i <= SQRT; i++) { f[i] = P % i; }
    for (int i = 1; i <= SQRT; i++) { f[i] += f[i - 1]; }
    std::vector<ll> r, s, t, b;
    for (ll i = SQRT; i >= 1; i--) {
        const ll S = (P + i) / (i + 1);
        const ll T = P / i;
        if (T >= S) {
            r.push_back(i), s.push_back(S), t.push_back(T);
            const ll sum = P * (T - S + 1) - (S + T) * (T - S + 1) / 2 * i;
            b.push_back(sum);
        }
    }
    s.push_back(P + 1);
    for (int i = 1; i < b.size(); i++) { b[i] += b[i - 1]; }
    for (int q = 0; q < Q; q++) {
        long long L, R;
        std::cin >> L >> R;
        L = (ll)(L), R = (ll)(R);
        if (R <= SQRT) {
            std::cout << (long long)(f[R] - f[L - 1]) << std::endl;
        } else if (L > P) {
            std::cout << (R - L + 1) * (L + R) / 2 << std::endl;
        } else {
            ll ans = (L > SQRT) ? 0 : f[SQRT] - f[L - 1];
            ans += (R > P) ? (R - P) * (R + P + 1) / 2 : 0;
            if (R > P) { R = P; }
            if (L <= SQRT) { L = SQRT + 1; }
            const ll lind = std::lower_bound(s.begin(), s.end(), L) - s.begin();
            const ll rind = std::upper_bound(t.begin(), t.end(), R) - t.begin() - 1;
            if (rind >= lind) { ans += b[rind] - b[lind - 1]; }
            const ll T = t[lind - 1];
            ll sum = (2 * P - r[lind - 1] * (L + T)) * (T - L + 1) / 2;
            ans += sum;
            const ll S = s[rind + 1];
            sum = (2 * P - r[rind + 1] * (S + R)) * (R - S + 1) / 2;
            ans += sum;
            std::cout << (long long)ans << std::endl;
        }
    }
    return 0;
}
0