結果

問題 No.752 mod数列
コンテスト
ユーザー Pachicobue
提出日時 2018-11-09 22:18:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,925 bytes
コンパイル時間 2,020 ms
コンパイル使用メモリ 200,040 KB
最終ジャッジ日時 2025-01-06 16:04:19
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 4 WA * 27
権限があれば一括ダウンロードができます

ソースコード

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