結果

問題 No.3331 Consecutive Cubic Sum
コンテスト
ユーザー にょぐた
提出日時 2025-08-17 16:09:49
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 23 ms / 5,000 ms
コード長 1,689 bytes
コンパイル時間 3,091 ms
コンパイル使用メモリ 286,124 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-02 20:50:43
合計ジャッジ時間 4,997 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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;
}

// r-lをkに固定したとき、合計値は{r^2(r+1)^2-(r-k-1)^2(r-k)^2}/2
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;
}

int main() {

    LL n;
    cin >> n;
    vector<pair<LL, LL>> ans;

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

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

    cout << ans.size() << "\n";
    for (auto e : ans) {
        cout << e.second << " " << e.first << "\n";
    }

}
0