結果

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

ソースコード

diff # 

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


using ll = long long;
using vll = vector<long long>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

#define reps(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define rep(i, n) reps(i, 0, n)
#define rrep(i, n) reps(i, 1, n + 1)
#define repd(i,n) for(ll i=n-1;i>=0;i--)
#define rrepd(i,n) for(ll i=n;i>=1;i--)
#define repsd(i, a, n) for(ll i=n;i>=a;i--)
#define fore(i,a) for(auto &i:a)

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

vll divisor(ll n) {
    vll ret;
    for (ll i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(begin(ret), end(ret));
    return ret;
}

ll sqrt_ceil(ll n) {
    ll res = sqrt(n);
    while((res + 1) * (res + 1) <= n) res++;
    return res;
}

ll cbrt_ceil(ll n) {
    ll res = cbrt(n);
    while ((res + 1) * (res + 1) * (res + 1) <= n) res++;
    return res;
}


int main() {

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

    // d = r-l+1 によって場合分け

    vll divisors;

    // Eが2のとき
    divisors = divisor(6 * n);
    // 6*n = d * (2*d*d-6*d*r-3*d+6*r*r+6*r+1)
    // r = sqrt((12*n/d-d*d+1)/3)+d-1/2
    fore(d, divisors) {
        ll r = (sqrt_ceil((12 * n / d - d * d + 1) / 3) + d - 1) / 2;
        if (6 * n != d * (2 * d * d - 6 * d * r - 3 * d + 6 * r * r + 6 * r + 1)) continue;
        ll l = r - d + 1;
        if(l<=0) continue;
        ans.push_back({ 2,l,r });
    }

    // Eが3のとき
    divisors = divisor(4 * n);
    // 4*n = d * (2*r-d+1)*(d*d-2*d*r-d+2*r*r+2*r)
    fore(d, divisors) {
        ll ng = cbrt_ceil(n) + 1, ok = d;
        if (ok > ng) continue;
        while (abs(ok - ng) > 1) {
            ll mid = ok + ng >> 1;
            if (4 * n >= mid * mid * (mid + 1) * (mid + 1) - (mid - d) * (mid - d) * (mid - d + 1) * (mid - d + 1)) ok = mid;
            else ng = mid;
        }
        if (4 * n != ok * ok * (ok + 1) * (ok + 1) - (ok - d) * (ok - d) * (ok - d + 1) * (ok - d + 1)) continue;
        ll r = ok;
        ll l = r - d + 1;
        ans.push_back({ 3,l,r });
    }

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

        ll 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, it - cum.begin() + 1, k });
            }

            k++;
        }


        E++;
    }

    

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

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

}
0