結果

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

ソースコード

diff # 

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


int main()
{
    using namespace std;
    using lint = long long;
    lint n;
    cin >> n;
    vector<tuple<int, lint, lint>> 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 numeric_limits<lint>::max();
        }
        return ans;
    };
    auto solve_2 = [&](lint n, int e) {
        vector<lint> pows;
        // c = floor(sqrt(n)) + 1
        lint c = *ranges::lower_bound(views::iota(0ll, n + 2), true, {}, [&](lint x) { return saturating_pow(x, 2) > n; });
        // for (lint i = 0;; ++i) {
        //     lint ip = saturating_pow(i, e);
        //     if (ip > n) break;
        //     c++;
        // }
        lint r = 1;
        lint current_sum = 0;
        for (lint l = 1; l < c; ++l) {
            while (r < c && current_sum + r * r <= n) {
                current_sum += r * r;
                r++;
            }
            if (current_sum == n) {
                ans.emplace_back(e, l, r - 1);
            }
            if (l < r) {
                current_sum -= l * l;
            }
        }
    };
    auto solve_two_pointer = [&](lint n, int e) {
        vector<lint> pows;
        for (lint i = 0;; ++i) {
            lint ip = saturating_pow(i, e);
            if (ip > n) break;
            pows.push_back(ip);
        }
        int c = pows.size();

        int r = 1;
        lint current_sum = 0;
        for (int l = 1; l < c; ++l) {
            while (r < c && current_sum + pows[r] <= n) {
                current_sum += pows[r];
                r++;
            }
            if (current_sum == n) {
                ans.emplace_back(e, l, r - 1);
            }
            if (l < r) {
                current_sum -= pows[l];
            }
        }
    };
    solve_2(n, 2);
    // solve_two_pointer(n, 2);
    for (int e = 3; e < 70; ++e) {
        solve_two_pointer(n, e);
    }
    ranges::sort(ans);

    cout << ans.size() << '\n';
    for (auto [e, l, r] : ans) {
        cout << e << ' ' << l << ' ' << r << '\n';
    }
}
0