結果

問題 No.3332 Consecutive Power Sum (Small)
コンテスト
ユーザー にょぐた
提出日時 2025-10-26 13:35:02
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 35 ms / 2,025 ms
コード長 3,935 bytes
コンパイル時間 3,447 ms
コンパイル使用メモリ 294,624 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-02 21:16:08
合計ジャッジ時間 5,964 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 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;
}

vector<LL> divisor(LL n) {
  vector<LL> 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;
}

int main() {

    LL n;
    cin >> n;
    vector<array<LL, 3>> ans;
    
    // Eが1のとき
    vector<LL> divisors = divisor(2*n);
    // 2*n = d * (2*r-d+1)
    for(auto d: divisors) {
        LL r = (2 * n / d + d - 1) / 2;
        if (2 * n != d * (2 * r - d + 1)) continue;
        if (r+1<=d) continue;
        LL l = r - d + 1;
        ans.push_back({ 1,l,r });
    }

    // 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) {
            bool flag = 0;
            LL tmp = 1;
            for(int i=0; i<E; i++){
              tmp *= k;
              if(tmp > n){
                flag = 1;
                break;
              }
            }
            if(flag) 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