用户输出
2系统信息
Exited with return code 0| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #48515 | #1243. zxh的高等数学 | Accepted | 100 | 18652 ms | 329252 K | C++ 11 / 1.3 K | 电类930-何卓霖 | 2021-05-14 23:28:08 |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e6;
const ll mod = 998244353;
ll n, ans;
ll mi[maxn + 10][41];
ll mx[maxn + 10];
void init() {
for (ll i = 2; i <= maxn; i++) {
mi[i][0] = 1;
for (ll j = 1; j <= 40; j++) {
mi[i][j] = mi[i][j - 1] * i;
if (mi[i][j] > n) {
mx[i] = j;
break;
}
}
}
}
ll inv(ll x, ll m) {
ll k = 1;
while (m) {
if (m & 1)
k *= x, k %= mod;
x *= x, x %= mod;
m >>= 1;
}
return k;
}
int main() {
// freopen("data.in","r",stdin);
// freopen("F.out","w",stdout);
scanf("%lld", &n);
init();
for (ll i = 2; i <= min(n, maxn); i++) {
ll tmp = 0;
for (ll j = 2; j < mx[i]; j++) {
tmp += (mi[i][j] - mi[i][j - 1]) * (j - 1) % mod;
tmp %= mod;
}
tmp += (n - mi[i][mx[i] - 1] + 1) * (mx[i] - 1) % mod;
tmp %= mod;
ans += tmp * i % mod;
ans %= mod;
}
if (n > maxn) {
ll tmp = 0;
n %= mod;
tmp = (maxn + 1 + n) % mod * (n - maxn) % mod * inv(2, mod - 2) % mod;
tmp = tmp * ((n + 1) % mod) % mod;
ans += tmp, ans %= mod;
ll tmp1 = 0, tmp2 = 0;
tmp1 = n % mod * (n + 1) % mod * (2 * n + 1) % mod * inv(6, mod - 2) % mod;
tmp2 = maxn * (maxn + 1) % mod * (2 * maxn + 1) % mod * inv(6, mod - 2) % mod;
ans = (ans - tmp1 + tmp2 + mod) % mod;
}
printf("%lld", ans);
return 0;
}