結果

問題 No.3333 Consecutive Power Sum (Large)
コンテスト
ユーザー Kude
提出日時 2025-11-02 23:05:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,148 ms / 10,000 ms
コード長 4,809 bytes
コンパイル時間 4,003 ms
コンパイル使用メモリ 331,420 KB
実行使用メモリ 55,308 KB
最終ジャッジ日時 2025-11-02 23:06:44
合計ジャッジ時間 60,056 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
外部呼び出し有り
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 63
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

using I = __int128;
vector<I> divisors(__int128 x) {
  char cmd[50] = "factor ";
  VI digits;
  for (auto t = x; t; t /= 10) digits.emplace_back(t % 10);
  if (digits.empty()) digits.emplace_back(0);
  int ptr = 7;
  for (int x : digits | views::reverse) cmd[ptr++] = '0' + x;
  cmd[ptr++] = '\0';
  std::array<char, 128> buffer;
  std::string result;
  FILE* pipe = popen(cmd, "r");
  assert(pipe);
  while (fgets(buffer.data(), static_cast<int>(buffer.size()), pipe) != nullptr) {
    result += buffer.data();
  }
  pclose(pipe);
  ptr = 0;
  while (result[ptr] != ':') ptr++;
  ptr++;
  istringstream ss(result.substr(ptr));
  vector<I> factors;
  for (string n_str; ss >> n_str;) {
    I n = 0;
    for (char c : n_str) n = 10 * n + (c - '0');
    factors.emplace_back(n);
  }
  vector<I> res{1};
  int csz = 1;
  I last = 0;
  for (I f : factors) {
    if (f != last) csz = res.size(), last = f;
    int ptr = ssize(res) - csz;
    rep(_, csz) res.emplace_back(res[ptr++] * f);
  }
  sort(all(res));
  return res;
}

string I2str(I x) {
  string res;
  while (x) res += '0' + x % 10, x /= 10;
  reverse(all(res));
  if (res.empty()) res = "0";
  return res;
}


constexpr long long INF = 1002003004005006007;
constexpr I IINF = I(INF) * INF / 8;

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string n_str;
  cin >> n_str;
  I n = 0;
  for (char c : n_str) n = 10 * n + (c - '0');
  // auto divs = divisors(n);
  // for (auto d : divs) {
  //   cout << I2str(d) << endl;
  // }

  vector<tuple<int, I, I>> ans;
  for (int e = 1;; e++) {
    // cout << e << endl;
    if (e == 1) {
      // (r-l+1)(l+r)/2
      I n2 = 2 * n;
      I t2 = n2 & -n2;
      int t = 0;
      while (!(t2 >> t & 1)) t++;
      I m = n2 >> t;
      auto divs = divisors(m);
      rep(i, ssize(divs)) {
        I D1 = divs[i], D2 = divs.end()[-1-i];
        for (auto [d1, d2] : {pair(D1 << t, D2), pair(D1, D2 << t)}) {
          if (d1 > d2) continue;
          I l = (d2 - d1) >> 1;
          I r = (d1 + d2 - 1) >> 1;
          ans.emplace_back(1, l + 1, r);
        }
      }
    } else if (e == 2) {
      I n6 = n * 6;
      auto divs = divisors(n6);
      for (I d1 : divs) {
        I d2 = n6 / d1;
        if ((d1 % 2 == 0) == (d2 % 2 == 0)) continue;
        if ((d1 % 3 == 0) == (d2 % 3 == 0)) continue;
        // constexpr auto mul = [](I x, I y) {
        //   if (__builtin_mul_overflow(x, y, &x)) x = INF;
        //   return x;
        // };
        auto f = [&](I l) {
          I r = l + d1 - 1;
          I tmp;
          I res = 0;
          if (__builtin_mul_overflow(l,l,&tmp)) return IINF;
          if (__builtin_mul_overflow(2,tmp,&tmp)) return IINF;
          if (__builtin_add_overflow(tmp,res,&res)) return IINF;
          if (__builtin_mul_overflow(l,r,&tmp)) return IINF;
          if (__builtin_mul_overflow(2,tmp,&tmp)) return IINF;
          if (__builtin_add_overflow(tmp,res,&res)) return IINF;
          res -= l;
          if (__builtin_mul_overflow(r,r,&tmp)) return IINF;
          if (__builtin_mul_overflow(2,tmp,&tmp)) return IINF;
          if (__builtin_add_overflow(tmp,res,&res)) return IINF;
          if (__builtin_add_overflow(r,res,&res)) return IINF;
          return res;
        };
        I l = 0, r = 1;
        while (f(r) < d2) l = r, r *= 2;
        while (r - l > 1) {
          I c = (l + r) >> 1;
          (f(c) < d2 ? l : r) = c;
        }
        if (f(r) == d2) ans.emplace_back(e, r, r + d1 - 1);
      }
    } else {
      if (I(1) << e > n) break;
      int l = 1;
      I now = 0;
      for (int r = 1;; r++) {
        I re = 1;
        rep(_, e) if (__builtin_mul_overflow(re, r, &re)) {
          re = n + 1;
          break;
        }
        if (re > n) break;
        now += re;
        while (now > n) {
          I le = 1;
          rep(_, e) le *= l;
          now -= le;
          l++;
        }
        if (now == n) ans.emplace_back(e, l, r);
      }
    }
  }
  cout << ans.size() << '\n';
  sort(all(ans));
  for (auto [e, l, r] : ans) cout << e << ' ' << I2str(l) << ' ' << I2str(r) << '\n';
}
0