結果

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

ソースコード

diff # 

//=================================
// Created on: 2018/11/09 21:30:39
//=================================
#include <bits/stdc++.h>
#define show(x) std::cerr << #x << " = " << (x) << std::endl
using ll = __int128_t;
std::istream& operator>>(std::istream& is, ll& v)
{
    std::string s;
    is >> s, v = 0;
    for (std::size_t i = 0; i < s.size(); i++) {
        if (isdigit(s[i])) { v = v * 10 + s[i] - '0'; }
    }
    if (s[0] == '-') { v *= -1; }
    return is;
}
std::ostream& operator<<(std::ostream& os, const ll& v)
{
    if (v == 0) { return (os << "0"); }
    __int128_t num = v;
    if (v < 0) { os << '-', num = -num; }
    std::string s;
    for (; num > 0; num /= 10) { s.push_back((char)(num % 10) + '0'); }
    reverse(s.begin(), s.end());
    return (os << s);
}
template <typename T, typename A>
std::ostream& operator<<(std::ostream& os, const std::vector<T, A>& v)
{
    os << "[";
    for (const auto& p : v) { os << p << ","; }
    return (os << "]\n");
}
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 + 1) + 1;
        const ll T = P / i;
        if (T >= S) {
            r.push_back(i), s.push_back(S), t.push_back(T);
            const ll sum = (2 * P - i * (S + T)) * (T - S + 1) / 2;
            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;
        if (R <= SQRT) {
            std::cout << f[R] - f[L - 1] << std::endl;
        } else if (L > P) {
            std::cout << (R - L + 1) * P << std::endl;
        } else {
            ll ans = (L > SQRT) ? 0 : f[SQRT] - f[L - 1];
            ans += (R > P) ? (R - P) * P : 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];
            } else if (lind - rind >= 2) {
                std::cout << (2 * P - (R + L)) * (R - L + 1) / 2 << std::endl;
                continue;
            }
            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 << ans << std::endl;
        }
    }
    return 0;
}
0