LibreOJ 6181 某个套路求和题

这题其实真的很套路……

首先考虑一下 f(n) 的定义。
易得 f(n)={(−1)[n is prime],∀d>1 d2⧸|n0,∃d>1 d2|n

证明：
当 n 有平方因子时 f(n) 显然为 0。
否则考虑 (−1) 的指数，即 ω(n)∑i=0i(ω(n)i)，其中 ω(n) 表示 n 的不同质因子个数。
由于 (ω(n)i)=(ω(n)ω(n)−i)，故 ω(n)∑i=0i(ω(n)i)=12ω(n)∑i=0ω(n)(ω(n)i)=2ω(n)−1ω(n)。
仅当 ω(n)=1 即 n 为质数时该式为 1，其余情况该式均为偶数。
证毕。

于是可以考虑算出无平方因子的数的个数，然后减去质数的贡献。
后者是一个经典问题，std 使用了 O(n3/4logn) 的 Min_25 筛解决，实际上还有诸如 Meissel-Lehmer 很多方法。

前者相当于求 n∑i=1μ2(i)。
考虑令 msf(n)=maxd2|nd 即 n 的最大平方因子。
则 n∑i=1μ2(i)=n∑i=1[msf(i)=1]=n∑i=1∑d|msf(i)μ(d)=n∑d=1μ(d)∑d|msf(i)1

注意到 d|msf(i) 等价于 d2|i，故 n∑d=1μ(d)∑d|msf(i)1=n∑d=1μ(d)∑d2|i1=⌊√n⌋∑d=1μ(d)⌊nd2⌋

于是线性筛出 ⌊√n⌋ 以内的 μ 值，此部分即可 O(√n) 求出。

（题外话：这个函数其实来自于 Elementary Number Theory and Its Applications 的某一道习题）

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const long long N = 1e10;
const int MX = 1e5;
const int mod = 998244353;
const int inv = 499122177;
long long n;
int lim;
int vis[MX + 5],prime[MX + 5],cnt,mu[MX + 5];
int tot,le[MX + 5],ge[MX + 5];
long long lis[2 * MX + 5];
int G[2 * MX + 5];
int ans;
inline int &id(long long x)
{
    return x <= lim ? le[x] : ge[n / x];
}
int main()
{
    mu[1] = 1;
    for(register int i = 2;i <= MX;++i)
    {
        if(!vis[i])
            mu[prime[++cnt] = i] = mod - 1;
        for(register int j = 1;j <= cnt && i * prime[j] <= MX;++j)
        {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))
                break;
            mu[i * prime[j]] = mod - mu[i];
        }
    }
    scanf("%lld",&n),lim = sqrt(n);
    for(register long long l = 1,r;l <= n;l = r + 1)
    {
        r = n / (n / l);
        lis[id(n / l) = ++tot] = n / l;
        G[tot] = (n / l % mod - 1 + mod) % mod;
    }
    for(register int k = 1;k <= cnt;++k)
    {
        int p = prime[k];
        long long s = (long long)p * p;
        for(register int i = 1;lis[i] >= s;++i)
            G[i] = (G[i] - (G[id(lis[i] / p)] - (k - 1) + mod) % mod + mod) % mod;
    }
    for(register int i = 1;i <= lim;++i)
        ans = (ans + (n / i / i) * mu[i] % mod) % mod;
    ans = (ans - 2LL * G[1] % mod + mod) % mod;
    printf("%d\n",ans);
}