結果

問題 No.3332 Consecutive Power Sum (Small)
コンテスト
ユーザー wasd314
提出日時 2025-10-20 23:38:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 22 ms / 2,025 ms
コード長 2,408 bytes
コンパイル時間 1,438 ms
コンパイル使用メモリ 142,356 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-02 21:13:49
合計ジャッジ時間 3,628 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 52
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <numeric>
#include <ranges>
#include <tuple>
#include <vector>

int main()
{
    using namespace std;
    using lint = long long;
    lint n;
    cin >> n;
    using T = tuple<int, lint, lint>;
    auto solve_1 = [](lint n) {
        vector<T> ans;
        lint n2 = n * 2;
        for (lint w = 1; w * w <= n2; ++w) {
            if (n2 % w) continue;
            lint wl = n2 / w;
            if (w >= wl || (w + wl) % 2 == 0) continue;
            lint l = (wl - w + 1) / 2;
            ans.emplace_back(1, l, l + w - 1);
        }
        ranges::reverse(ans);
        return ans;
    };
    auto solve_2 = [](lint n) {
        lint m = 1;
        for (int i = 30; i-- > 0;) {
            lint m2 = m + (1ll << i);
            if (m2 * m2 <= n) m = m2;
        }
        assert(m * m <= n);
        assert(n < (m + 1) * (m + 1));
        vector<T> ans;
        lint r = 1, s = 0;
        for (lint l = 1; l <= m; ++l) {
            while (s + r * r <= n) {
                s += r * r;
                r++;
            }
            if (s == n) ans.emplace_back(2, l, r - 1);
            s -= l * l;
        }
        return ans;
    };
    auto saturating_pow = [](lint a, int e) {
        lint ans = 1;
        for (int i = 0; i < e; ++i) {
            if (__builtin_mul_overflow(ans, a, &ans)) return std::numeric_limits<lint>::max();
        }
        return ans;
    };
    auto solve_e = [&saturating_pow](lint n, int e) {
        vector<T> ans;
        vector<lint> acc{0};
        for (lint i = 1; saturating_pow(i, e) <= n; ++i) {
            acc.push_back(acc.back() + saturating_pow(i, e));
        }
        map<lint, lint> to_l;
        for (auto [l, s] : acc | views::enumerate) to_l[s] = l;
        for (auto [r, s] : acc | views::enumerate) {
            if (r == 0) continue;
            auto it = to_l.find(s - n);
            if (it == to_l.end()) continue;
            lint l = it->second + 1;
            if (l >= 1) ans.emplace_back(e, l, r);
        }
        return ans;
    };
    vector<T> ans = solve_1(n);
    for (auto t : solve_2(n)) ans.push_back(t);
    for (int e = 3; saturating_pow(2, e) <= n; ++e) {
        for (auto t : solve_e(n, e)) ans.push_back(t);
    }
    cout << ans.size() << '\n';
    for (auto [e, l, r] : ans) {
        cout << e << ' ' << l << ' ' << r << '\n';
    }
}
0