結果

問題 No.752 mod数列
コンテスト
ユーザー 梧桐
提出日時 2026-01-23 02:51:54
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 56 ms / 2,000 ms
コード長 1,267 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 763 ms
コンパイル使用メモリ 92,808 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-23 02:51:59
合計ジャッジ時間 4,125 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;

int p, q, l, r;

vector<int> seg_l, seg_r, seg_q;
vector<LL> seg_sum;

LL CalcSum(int rr) {
    if (rr <= 0 || p == 0) return 0LL;
    if (rr >= p) return seg_sum.back() + 1LL * (rr - p) * p;
    int idx = lower_bound(seg_r.begin(), seg_r.end(), rr) - seg_r.begin();
    LL base = idx == 0 ? 0LL : seg_sum[idx - 1];
    int ll = seg_l[idx], qv = seg_q[idx];
    int len = rr - ll + 1;
    LL sum = 1LL * len * p - 1LL * len * qv * (ll + rr) / 2;
    return base + sum;
}

int main() {
    // freopen("mod.in", "r", stdin);
    // freopen("mod.out", "w", stdout);

    scanf("%d%d", &p, &q);
    if (p > 0) {
        for (int ll = 1; ll <= p; ) {
            int v = p / ll, rr = p / v;
            seg_l.push_back(ll);
            seg_r.push_back(rr);
            seg_q.push_back(v);
            int len = rr - ll + 1;
            LL sum = 1LL * len * p - 1LL * len * v * (ll + rr) / 2;
            LL total = (seg_sum.empty() ? 0 : seg_sum.back()) + sum;
            seg_sum.push_back(total);
            ll = rr + 1;
        }
    }
    while (q--) {
        scanf("%d%d", &l, &r);
        printf("%lld\n", CalcSum(r) - CalcSum(l - 1));
    }

    return 0;
}
0