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));
}