結果

問題 No.752 mod数列
ユーザー PachicobuePachicobue
提出日時 2018-11-09 23:11:36
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,847 bytes
コンパイル時間 2,297 ms
コンパイル使用メモリ 210,192 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-21 06:46:10
合計ジャッジ時間 7,665 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,816 KB
testcase_01 AC 4 ms
6,820 KB
testcase_02 AC 4 ms
6,816 KB
testcase_03 AC 4 ms
6,816 KB
testcase_04 AC 4 ms
6,816 KB
testcase_05 AC 4 ms
6,820 KB
testcase_06 AC 4 ms
6,816 KB
testcase_07 AC 4 ms
6,816 KB
testcase_08 AC 4 ms
6,820 KB
testcase_09 AC 4 ms
6,816 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 182 ms
6,816 KB
testcase_16 AC 209 ms
6,816 KB
testcase_17 AC 251 ms
6,820 KB
testcase_18 WA -
testcase_19 AC 238 ms
6,816 KB
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 AC 243 ms
6,816 KB
testcase_30 AC 224 ms
6,816 KB
testcase_31 AC 4 ms
6,820 KB
testcase_32 AC 4 ms
6,820 KB
testcase_33 AC 6 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

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) / (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;
        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