結果
| 問題 | No.3505 Sum of Prod of Root |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-17 17:08:28 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 124 ms / 2,000 ms |
| + 65µs | |
| コード長 | 2,812 bytes |
| 記録 | |
| コンパイル時間 | 2,411 ms |
| コンパイル使用メモリ | 349,180 KB |
| 実行使用メモリ | 27,436 KB |
| 最終ジャッジ日時 | 2026-11-17 17:08:33 |
| 合計ジャッジ時間 | 4,959 ms |
|
ジャッジサーバーID (参考情報) |
judge4_0 / judge3_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 13 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
constexpr ll MOD = 998244353;
constexpr ll INV2 = 499122177;
constexpr ll INV6 = 166374059;
constexpr ll INV30 = 432572553;
ll mul(ll a, ll b) {
return a * b % MOD;
}
// F(x) = Σ(i * floor(sqrt(i))) (1 <= i <= x)
ll prefix(ll x) {
if (x <= 0) return 0;
// m = floor(sqrt(x))
ll m = sqrtl((long double)x);
// 浮動小数点誤差の補正
while ((i128)(m + 1) * (m + 1) <= x) ++m;
while ((i128)m * m > x) --m;
ll n = m - 1;
ll a = n % MOD;
ll b = (n + 1) % MOD;
ll c = (2 * n + 1) % MOD;
// S2 = Σj^2
ll s2 = mul(mul(mul(a, b), c), INV6);
// S3 = Σj^3
ll t = mul(mul(a, b), INV2);
ll s3 = mul(t, t);
// S4 = Σj^4
ll d = (3 * mul(a, a) % MOD
+ 3 * a % MOD + MOD - 1) % MOD;
ll s4 = mul(mul(mul(mul(a, b), c), d), INV30);
// 完全に含まれる区間
ll full = (2 * s4 + 3 * s3 + s2) % MOD;
// 最後の区間 [m^2, x]
ll m2 = m * m;
ll tail = mul(
mul(m % MOD, (m2 + x) % MOD),
(x - m2 + 1) % MOD
);
tail = mul(tail, INV2);
return (full + tail) % MOD;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
cin >> N;
// k >= 3 の完全累乗数をイベントとして列挙
// (a^k, a) を保存
vector<pair<ll, int>> events;
int max_a = 2;
for (int k = 3; k <= 59; ++k) {
for (ll a = 2;; ++a) {
i128 p = 1;
for (int j = 0; j < k && p <= N; ++j) {
p *= a;
}
if (p > N) break;
events.emplace_back((ll)p, (int)a);
max_a = max(max_a, (int)a);
}
}
sort(events.begin(), events.end());
// 逆元を前計算
vector<ll> inv(max_a + 1);
inv[1] = 1;
for (int i = 2; i <= max_a; ++i) {
inv[i] = MOD - mul(MOD / i, inv[MOD % i]);
}
ll ans = 0;
ll weight = 1;
ll prev_sum = 0;
for (size_t j = 0; j < events.size();) {
ll pos = events[j].first;
// 次のイベント直前までの区間和
ll next_sum = prefix(pos - 1);
ll interval = (next_sum - prev_sum + MOD) % MOD;
ans = (ans + mul(weight, interval)) % MOD;
prev_sum = next_sum;
// 同じ位置で発生するイベントをすべて処理
while (j < events.size() && events[j].first == pos) {
ll a = events[j].second;
// (a-1) -> a に変化
weight = mul(weight, mul(a, inv[a - 1]));
++j;
}
}
// 最後のイベントから N まで
ll tail = (prefix(N) - prev_sum + MOD) % MOD;
ans = (ans + mul(weight, tail)) % MOD;
cout << ans << '\n';
return 0;
}