LibreOJ 6714.Stupid Product

小清新杜教筛水题~(

考虑 \(f(n)\) 的递推式,可得 \[ f(n) = [n=1] + \sum\limits_{d|n,d < n} f(d) \]

考虑容斥掉第二项的贡献,即 \[ f(n) - \sum\limits_{d|n,d < n} f(d) = \sum\limits_{d|n} (-1)^{[d < n]} f(d) = [n=1] \]

注意到其中的 \([d < n]\) 可以被写作 \([\frac nd \ne 1]\)
也即可以表示为狄利克雷卷积的形式: \[ \sum\limits_{d|n} f(d)g\left(\frac nd\right) = [n=1] \]

其中 \(g(n) = (-1)^{[n \ne 1]}\)

因此考虑杜教筛求出 \(f\) 即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <cstring>
#define add(x,y) (x + y >= mod ? x + y - mod : x + y)
#define dec(x,y) (x < y ? x - y + mod : x - y)
using namespace std;
const long long N = 1e10;
const int MX = 6e5;
const int mod = 998244353;
long long n;
int f[MX + 5],s[MX + 5];
inline int &mem(long long x)
{
return s[n / x];
}
int calc(long long n)
{
if(n <= MX)
return f[n];
if(~mem(n))
return mem(n);
int ret = 1;
for(register long long l = 2,r;l <= n;l = r + 1)
{
r = n / (n / l);
ret = (ret + (r - l + 1) * calc(n / l) % mod) % mod;
}
return mem(n) = ret;
}
int main()
{
memset(s,-1,sizeof s),f[1] = 1;
for(register int i = 1;i <= MX;++i)
{
for(register int j = i << 1;j <= MX;j += i)
f[j] = add(f[j],f[i]);
f[i] = add(f[i],f[i - 1]);
}
scanf("%lld",&n);
printf("%d\n",calc(n));
}