結果

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

ソースコード

diff #
raw source code 

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

using namespace std;

typedef long long LL;

LL p, l, r;
int q;

vector<LL> segL, segR, segQ, pref;

LL sum_pref(LL n) {
    if (n <= 0 || p == 0) return 0LL;
    if (n >= p) return pref.back() + (n - p) * p;
    int id = lower_bound(segR.begin(), segR.end(), n) - segR.begin();
    LL base = (id == 0 ? 0LL : pref[id - 1]);
    LL L = segL[id], qv = segQ[id];
    LL len = n - L + 1;
    LL sum = len * p - qv * (L + n) * len / 2;
    return base + sum;
}

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

    scanf("%lld%d", &p, &q);
    if (p > 0) {
        for (LL n = 1; n <= p; ) {
            LL qv = p / n, r = p / qv;
            segL.push_back(n);
            segR.push_back(r);
            segQ.push_back(qv);
            LL len = r - n + 1;
            LL sum = len * p - qv * (n + r) * len / 2;
            LL total = (pref.empty() ? 0 : pref.back()) + sum;
            pref.push_back(total);
            n = r + 1;
        }
    }
    while (q--) {
        scanf("%lld%lld", &l, &r);
        printf("%lld\n", sum_pref(r) - sum_pref(l - 1));
    }

    return 0;
}
0