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

• 問題: No.3505 Sum of Prod of Root
• ユーザー: KowerKoint2010
• 提出日時: 2026-04-19 08:03:55
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 294 ms / 2,000 ms
• コード長: 2,706 bytes
• コンパイル時間: 2,478 ms
• コンパイル使用メモリ: 340,892 KB
• 実行使用メモリ: 7,972 KB
• 最終ジャッジ日時: 2026-04-19 08:04:02
• 合計ジャッジ時間: 4,217 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_1

ファイルパターン	結果
sample	AC * 1
other	AC * 13

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i, n) for(ll i =0; i < ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B>
bool chmax(A& a, B b) { return a<b && (a=b, true); }
template <class A, class B>
bool chmin(A& a, B b) { return b<a && (a=b, true); }

template <int MD, int g = 3>
struct ModInt {
  using M = ModInt;
  const static inline M G = g;
  unsigned int v;
  ModInt() : v(0) {}
  ModInt(ll w) : v(w % MD + MD) {
    if(v >= MD) v -= MD;
  }
  static M raw(unsigned int v) {
    M res;
    res.v = (v < MD) ? v : v - MD;
    return res;
  }
  explicit operator bool() const {
    return v != 0;
  }
  M operator-() const {
    return M() - *this;
  }
  M operator+(M r) const {
    return raw(v + r.v);
  }
  M operator-(M r) const {
    return raw(v + MD - r.v);
  }
  M operator*(M r) const {
    return raw(ll(v) * r.v % MD);
  }
  M operator/(M r) const {
    return *this * r.inv();
  }
  M& operator+=(M r) {
    return *this = *this + r;
  }
  M& operator-=(M r) {
    return *this = *this - r;
  }
  M& operator*=(M r) {
    return *this = *this * r;
  }
  M& operator/=(M r) {
    return *this = *this / r;
  }
  bool operator==(M r) const {
    return v == r.v;
  }
  M pow(ll n) const {
    M x = *this, r = 1;
    while (n) {
      if (n & 1) r *= x;
      x *= x;
      n >>= 1;
    }
    return r;
  }
  M inv() const {
    return pow(MD - 2);
  }
  friend ostream& operator<<(ostream& os, M r) {
    return os << r.v;
  }
};
// using Mint = ModInt<998244353, 3>;


void testcase() {
  ll n; cin >> n;
  auto ipow = [&](ll a, ll k) {
    __int128_t res = 1;
    REP(i, k) {
      res *= a;
      if(res >= INF) return INF;
    }
    return (ll)res;
  };
  auto iroot = [&](ll a, ll k) {
    ll res = 0;
    for(int b = 60; b >= 0; b--) {
      if(ipow(res | 1LL<<b, k) <= a) res |= 1LL<<b;
    }
    return res;
  };
  using MI = ModInt<998244353>;
  MI inv20 = MI(20).inv();
  MI inv2 = MI(2).inv();
  auto under2 = [&](ll a) {
    if(a == 0) return MI(0);
    ll r = iroot(a, 2);
    MI ans = inv20 * (r-1) * r * (r+1) * (MI(8)*r*r - MI(5)*r - MI(2));
    ans += MI(r) * inv2 * (r*r + a) * (a - r*r + 1);
    return ans;
  };
  auto solve = [&](auto&& self, ll l, ll r, ll k) -> MI {
    if(k == 1) return inv2 * (l + r) * (r - l + 1);
    if(k == 2) return under2(r) - under2(l-1);
    MI res = 0;
    for(ll s = l, sr = iroot(l, k); s <= r;) {
      ll t = ipow(sr+1, k);
      res += MI(sr) * self(self, s, min(t-1, r), k-1);
      s = t;
      sr++;
    }
    return res;
  };
  cout << solve(solve, 1, n, 60) << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  testcase();
}