LibreOJ 6714 Stupid Product

小清新杜教筛水题~（

考虑 f(n) 的递推式，可得 f(n)=[n=1]+∑d|n,d<nf(d)

考虑容斥掉第二项的贡献，即 f(n)−∑d|n,d<nf(d)=∑d|n(−1)[d<n]f(d)=[n=1]

注意到其中的 [d<n] 可以被写作 [nd≠1]。
也即可以表示为狄利克雷卷积的形式： ∑d|nf(d)g(nd)=[n=1]

其中 g(n)=(−1)[n≠1]。

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

代码：

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