#1158065 (C++23) No.3505 Sum of Prod of Root

• 問題: No.3505 Sum of Prod of Root
• ユーザー: Enderaoe Lyther
• 提出日時: 2026-04-17 21:53:48
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,231 bytes
• コンパイル時間: 540 ms
• コンパイル使用メモリ: 77,072 KB
• 実行使用メモリ: 13,056 KB
• 最終ジャッジ日時: 2026-04-17 21:54:39
• 合計ジャッジ時間: 11,474 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_1

ファイルパターン	結果
sample	-- * 1
other	TLE * 2 -- * 11

ソースコード

#include <cmath>
#include <cstdio>
using namespace std;
using int64 = long long;
const int64 MOD = 998244353;
const int64 INV2 = (MOD + 1) / 2;

int64 addmod(int64 a, int64 b) {
  int64 s = a + b;
  if (s >= MOD)
    s -= MOD;
  return s;
}
int64 mulmod(int64 a, int64 b) { return (__int128)a * b % MOD; }

/* true iff base^k <= limit; avoids __int128 overflow on p *= base */
static inline bool pow_le64(int64 base, int k, int64 limit) {
  if (base <= 1) {
    if (base == 0)
      return 0 <= limit;
    return 1 <= limit;
  }
  __int128 p = 1;
  __int128 L = (__int128)limit;
  for (int t = 0; t < k; ++t) {
    if (p > L / base)
      return false;
    p *= base;
  }
  return p <= L;
}

static int64 iroot_floor_bin(int64 n, int k) {
  int64 lo = 0, hi = n + 1;
  while (lo + 1 < hi) {
    int64 mid = lo + (hi - lo) / 2;
    if (pow_le64(mid, k, n))
      lo = mid;
    else
      hi = mid;
  }
  return lo;
}

static int64 iroot_floor_fast(int64 n, int k) {
  if (k == 2) {
    int64 r = (int64)sqrt((long double)n);
    if (r < 1)
      r = 1;
    while ((unsigned __int128)(r + 1) * (r + 1) <= (unsigned __int128)n)
      ++r;
    while ((unsigned __int128)r * r > (unsigned __int128)n)
      --r;
    return r;
  }
  int64 r = (int64)pow((long double)n, 1.0L / k);
  if (r < 1)
    r = 1;
  for (int z = 0; z < 70; ++z) {
    if (pow_le64(r + 1, k, n))
      ++r;
    else
      break;
  }
  for (int z = 0; z < 70; ++z) {
    if (!pow_le64(r, k, n))
      --r;
    else
      break;
  }
  if (!pow_le64(r, k, n) || pow_le64(r + 1, k, n))
    return iroot_floor_bin(n, k);
  return r;
}

static inline int64 end_from_j(int64 j, int k, int64 N, const int64 *end1) {
  if (j == 1)
    return end1[k];
  __int128 b = (__int128)(j + 1);
  __int128 pk = 1;
  for (int t = 0; t < k; ++t) {
    if (pk > (__int128)N / b)
      return N;
    pk *= b;
  }
  int64 end = (int64)(pk - 1);
  return end > N ? N : end;
}

/* smallest k>=1 with i < 2^k  => for k>=k0, floor(i^{1/k})==1 */
static inline int k0_pow2_gt(int64 i) {
  int k = 1;
  for (; k <= 60; ++k) {
    if ((__int128)i < ((__int128)1 << k))
      break;
  }
  return k;
}

int64 tri_mod(int64 n) {
  if (n <= 0)
    return 0;
  return mulmod(mulmod(n % MOD, (n + 1) % MOD), INV2);
}

int64 sum_i_mod(int64 L, int64 R) {
  if (L > R)
    return 0;
  return (tri_mod(R) - tri_mod(L - 1) + MOD) % MOD;
}

int main() {
  int64 N;
  scanf("%lld", &N);

  int64 end1[61];
  for (int k = 2; k <= 60; ++k) {
    __int128 p = 1;
    for (int t = 0; t < k; ++t)
      p *= 2;
    if (p - 1 > (__int128)N)
      end1[k] = N;
    else
      end1[k] = (int64)(p - 1);
  }

  int64 ans = 0;
  for (int64 i = 1; i <= N;) {
    int64 R = N;
    int64 g = 1;
    const int k0 = k0_pow2_gt(i);
    for (int k = 2; k < k0 && k <= 60; ++k) {
      int64 j = iroot_floor_fast(i, k);
      int64 e = end_from_j(j, k, N, end1);
      if (e < R)
        R = e;
      if (j >= 2)
        g = mulmod(g, j % MOD);
    }
    const int k_lo = k0 > 2 ? k0 : 2;
    if (k_lo <= 60) {
      int64 e = end1[k_lo];
      if (e < R)
        R = e;
    }
    if (R < i)
      R = i;
    ans = addmod(ans, mulmod(g, sum_i_mod(i, R)));
    i = R + 1;
  }
  printf("%lld\n", (long long)ans);
  return 0;
}