某个套路求和题
从前有个 alpha1022，他在看某本奇妙的书的时候想到了这样一个函数：
[f(n) = prod_{d|n} mu(d)
]
然后就有了这样一个问题：
[sum_{i=1}^n f(i) mod 998244353
]
然后他就把这个问题扔给了你。
对于 (100\%) 的数据，(n le 10^{10})。
题解
http://jklover.hs-blog.cf/2020/04/19/Loj-6181-某个套路求和题/
考虑化简(f(n)=prod_{d|n} mu(d))。
当(n)有平方因子时，(f(n) = 0)，否则我们考虑有几个(mu(d)=-1)，就可以算出(mu(n))。
记(n)有(omega(n))种不同的质因子，由于(n)没有平方因子，所以各个质因子的次数都是(1)。
(d)是(n)的约数可以看做从(omega(n))个质因子中选出一些乘起来组成的，而(mu(d)=-1)等价于选了奇数个。
那么显然有(2^{omega(n)-1})种选法，只有当(n)为质数时有奇数个(mu(d)=-1)，其他情况都有偶数个。
于是可以得出
[ ext{ans}=sum_{i=1}^nmu^2(i) -sum_{i=1}^n 2 imes [iin P]
]
后者是(1)到(n)中质数个数的(2)倍，可以用Min_25筛求出.
考虑如何求(sum mu^2(i))，记(p(n)=max_{d^2|n} lbrace d brace)表示(n)的最大平方因子，则
[sum_{i=1}^n mu^2(i) \
=sum_{i=1}^n [p(i)=1] \
=sum_{d=1}^n mu(d) sum_{d|p(i)}1 \
=sum_{d=1}^nmu(d) sum_{d^2|i} 1\
=sum_{d=1}^n mu(d) lfloor frac n {d^2}
floor
]
于是筛出(sqrt n)以内的(mu)，就可以在(O(sqrt n))内计算出(sum mu^2(i))了。
CO int N=2e5+10,mod=998244353;
int prime[N],num,mu[N];
int pos[N],idx,ref1[N],ref2[N],H[N];
signed main(){
int n=read<int>(),m=ceil(sqrt(n));
mu[1]=1;
for(int i=2;i<=m;++i){
if(!prime[i]) prime[++num]=i,mu[i]=-1;
for(int j=1;j<=num and i*prime[j]<=m;++j){
prime[i*prime[j]]=1;
if(i%prime[j]==0) break;
mu[i*prime[j]]=-mu[i];
}
}
for(int l=1,r;l<=n;l=r+1){
r=n/(n/l);
pos[++idx]=n/l;
if(n/l<=m) ref1[n/l]=idx;
else ref2[n/(n/l)]=idx;
}
for(int i=1;i<=idx;++i) H[i]=pos[i]-1;
for(int j=1;j<=num;++j)
for(int i=1;i<=idx and prime[j]*prime[j]<=pos[i];++i){
int k=pos[i]/prime[j];
if(k<=m) k=ref1[k];
else k=ref2[n/k];
H[i]-=H[k]-(j-1);
}
int ans=0;
for(int i=1;i*i<=n;++i) ans+=mu[i]*(n/(i*i));
ans-=2*H[1];
printf("%lld
",(ans%mod+mod)%mod);
return 0;
}