結果

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

ソースコード

diff # 

#include <algorithm>
#include <iostream>
#include <numeric>
#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;
        lint c = 0;
        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