結果

問題 No.3332 Consecutive Power Sum (Small)
コンテスト
ユーザー にょぐた
提出日時 2025-08-17 17:56:18
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,220 bytes
コンパイル時間 3,271 ms
コンパイル使用メモリ 290,244 KB
実行使用メモリ 7,724 KB
最終ジャッジ日時 2025-11-02 20:51:20
合計ジャッジ時間 5,032 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 52
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
#include<iostream>
using namespace std;

using LL = __int128;
istream& operator>>(istream& is, LL& v)
{
    string s;
    is >> s;
    v = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (isdigit(s[i])) { v = v * 10 + s[i] - '0'; }
    }
    if (s[0] == '-') { v *= -1; }
    return is;
}
ostream& operator<<(ostream& os, const LL& v)
{
    if (v == 0) { return (os << "0"); }
    LL num = v;
    if (v < 0) {
        os << '-';
        num = -num;
    }
    string s;
    for (; num > 0; num /= 10) { s.push_back((char)(num % 10) + '0'); }
    reverse(s.begin(), s.end());
    return (os << s);
}

LL cbrt128(LL n) {
    LL ng = 0, ok = 1;
    while (ok * ok * ok <= n) ok *= 2;
    while (ok - ng > 1) {
        LL mid = (ok + ng) / 2;
        LL tmp = mid * mid * mid;
        if (tmp >= n) ok = mid;
        else ng = mid;
    }
    return ok;
}

LL sqrt128(LL n) {
    LL ng = 0, ok = 1;
    while (ok * ok <= n) ok *= 2;
    while (ok - ng > 1) {
        LL mid = (ok + ng) / 2;
        LL tmp = mid * mid;
        if (tmp >= n) ok = mid;
        else ng = mid;
    }
    return ok;
}

// r-lをkに固定したとき、二乗和は{r*(r+1)*(2*r+1)-(r-k-1)*(r-k)*(2*r-2*k-1)}/6
LL f2(LL r, LL k) {
    LL res = (r * (r + 1) * (2 * r + 1) - (r - k - 1) * (r - k) * (2 * r - 2 * k - 1)) / 6;
    return res;
}

// r-lをkに固定したとき、三乗和は{r^2(r+1)^2-(r-k-1)^2(r-k)^2}/4
LL f3(LL r, LL k) {
    LL res = (r * r * (r + 1) * (r + 1) - (r - k - 1) * (r - k - 1) * (r - k) * (r - k)) / 4;
    return res;
}

LL pow_int(LL x, LL p) {
    LL res = 1;
    for (LL i = 0; i < p; i++) res *= x;
    return res;
}

int main() {

    LL n;
    cin >> n;
    vector<array<LL, 3>> ans;

    // Eが2のとき
    LL k = 0;
    while (true) {
        if (f2(k + 1, k) > n) break;
        LL limit = sqrt128(n) + 2;
        LL ok = k + 1, ng = limit;
        while (ng - ok > 1) {
            LL mid = ok + ng >> 1;
            if (f2(mid, k) > n) ng = mid;
            else ok = mid;
        }

        if (f2(ok, k) == n) ans.push_back({ 2, ok - k, ok });
        k++;
    }

    // Eが3のとき
    k = 0;
    while (true) {
        if (f3(k + 1, k) > n) break;
        LL limit = cbrt128(n) + 2;
        LL ok = k + 1, ng = limit;
        while (ng - ok > 1) {
            LL mid = ok + ng >> 1;
            if (f3(mid, k) > n) ng = mid;
            else ok = mid;
        }

        if (f3(ok, k) == n) ans.push_back({ 3, ok - k, ok });
        k++;
    }

    // Eが4以上のとき
    LL E = 4;
    while (true) {
        if (pow_int(2, E) > n) break;
        vector<LL> cum;
        LL sum = 0;

        k = 0;
        while (true) {
            LL tmp = pow_int(k, E);
            if (tmp > n) break;
            sum += tmp;
            cum.push_back(sum);
            auto it = lower_bound(cum.begin(), cum.end(), sum - n);
            if (it != cum.end() && *it == sum - n) {
                ans.push_back({ E, k, it - cum.begin() + 1 });
            }
            k++;
        }
        E++;
    }

    sort(ans.begin(), ans.end());

    cout << ans.size() << "\n";
    for (auto e : ans) {
        cout << e[0] << " " << e[1] << " " << e[2] << "\n";
    }

}
0