function
For $n=p_{1}^{k_1} p_{2}^{k_2} cdots p_{m}^{k_m}$ , define $f(n)=k_1 +k_2 + cdots + k_m$, please calculate$ sum_{i=1}^n f(i!) % 998244353$
Input
There is a single integer $n$($1 le n le 10^{10}$).
Output
Print a single line containing an integer, denoting the ans.
样例输入
10
样例输出
66
题意
见题面描述
解决方案
。。。。。。。。。。。。。。。。。。。。
min25筛好难啊，比杜教筛难了一个等级…….。
杜教筛其实就是基于狄利克雷卷积和常用的积性函数进行求和变换的一个套路，代码敲起来也比较简单，感觉和筛搭不上什么关系……。
min25筛才是名副其实的筛法的思想，然后形式上是一个 $dp$ 的转移方程，理解起来有挺大的难度，代码也不是很好写。
推荐两个教程：
min25筛要记住两个重要的公式：
首先，很显然有 $f(ab) = f(a) + f(b)$ ，所以有：
由 (1) 得到 (2) 只需要考虑每一个 $f(i)$ 的贡献即可，(2) 到 (3) 是简单的拆分。
好了，接下来是重头戏。
考虑 $sum_{i=1}^{n}f(i)$ ，先说结论：
证明：
考虑到 $f$ 的定义,，若 $i = p_1^{k_1}p_2^{k_2}…p_m^{k_m}$ ，则 $f(i) = k_1 + k_2 + … + k_m$ ，意思就是，对于 $i$ 来说，若其被 $p_j$ 整除，则答案要加 $1$ ，被 $p_j^2$ 整除，再加 $1$ ，一直到 $p_j^{k_j} $ ，总共加了 $k_j$ 个 $1$，所以我们只需要对每一个质数及其次幂的贡献考虑，$[1, n]$ 的范围内有多少个数是该质数及其次幂的倍数。
同理，$icdot f(i) = i times (k_1 + k_2 + … + k_m)$ ，每有一个质数或其次幂整除 $i$ ，则该式要多加上一个 $i$ ，所以有：
公式推完之后，接下来考虑怎么计算。
把质数分成两部分，一部分是小于等于 $sqrt{n}$ 的，另一部分是大于 $sqrt{n}$ 的，小于等于的一部分的贡献可以直接利用上面的式子暴力计算，但是，对于大于的那一部分，是不能直接求得，我们不可能把到 $1e10$ 的质数全部求出来，注意到，对于大于 $sqrt{n}$ 的那一部分质数，公式里的 $t$ 只能等于 $1$ ，化简之后即为：
其中 $g1(a, b)$ 表示 $[1, a]$ 的数被第 $b$ 个质数筛过之后还剩下多少个数，$g2(a, b)$ 表示 $[1, a]$ 的数被第 $b$ 个质数筛过之后剩下的数的和。
这两个 $g$ 的求法是min25筛的拿手好戏。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 100;
const ll mod = 998244353;
bool vis[maxn];
int prime[maxn];
ll a[maxn << 1];
ll g1[maxn << 1];
ll g2[maxn << 1];
ll f[maxn];
ll inv2, n, sq;
int m, tot;
void eular() {
vis[0] = vis[1] = true;
for (int i = 2; i < maxn; i++) {
if (!vis[i]) {
prime[++tot] = i;
}
for (int j = 1; j <= tot && i * prime[j] < maxn; j++) {
vis[i * prime[j]] = true;
if (i % prime[j] == 0) {
break;
}
}
}
for (int i = 1; i <= tot; i++) {
f[i] = (f[i - 1] + prime[i]) % mod;
}
}
int id(ll x) { return x <= sq ? x : m - n / x + 1; }
int main() {
eular();
inv2 = (mod + 1) / 2;
scanf("%lld", &n);
sq = sqrt(n + 1);
for (ll l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
a[++m] = r;
g1[m] = (r - 1) % mod;
g2[m] = (r + 2) % mod * (r - 1) % mod * inv2 % mod;
}
for (int i = 1; i <= tot && prime[i] <= sq; i++) {
ll tmp = 1ll * prime[i] * prime[i];
for (int j = m; a[j] >= tmp; j--) {
g1[j] -= (g1[id(a[j] / prime[i])] - (i - 1)) % mod;
g2[j] -= prime[i] * (g2[id(a[j] / prime[i])] - f[i - 1]) % mod;
g1[j] %= mod;
g2[j] %= mod;
if (g1[j] < 0) {
g1[j] += mod;
}
if (g2[j] < 0) {
g2[j] += mod;
}
}
}
ll ans1 = 0;
ll ans2 = 0;
for (ll l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
ll t1 = g1[id(r)] - g1[id(l - 1)];
ll t2 = g2[id(r)] - g2[id(l - 1)];
ans1 += (n / l) % mod * t1 % mod;
ans2 += (n / l) % mod * (n / l + 1) % mod * inv2 % mod * t2 % mod;
ans1 %= mod;
ans2 %= mod;
}
for (int i = 1; i <= tot && prime[i] <= sq; i++) {
for (ll tmp = 1ll * prime[i] * prime[i]; tmp <= n; tmp *= prime[i]) {
ans1 += n / tmp;
ans1 %= mod;
ans2 += (n / tmp) % mod * (n / tmp + 1) % mod * tmp % mod * inv2 % mod;
ans2 %= mod;
}
}
ans1 = (n + 1) % mod * ans1 % mod;
if (ans1 < 0) {
ans1 += mod;
}
if (ans2 < 0) {
ans2 += mod;
}
ll ans = (ans1 - ans2 + mod) % mod;
printf("%lldn", ans);
return 0;
}
近期评论