筛法瞎写

看见APJifengc在写min25筛发现我这个东西都不会了。赶紧复习了一把去写点题。写一个更一个。

loj6682 梦中的数论

答案显然 \(\frac 12\sum_{i=1}^n\binom{d(i)}{2}=\frac 12\sum_{i=1}^nd^2(i)-d(i)\) 。推导略，以前好像写过。

对了 \(\sum_{i=1}^nd(i)\) 是个傻逼问题，我拿这个诈骗joke3579然后他被骗了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int mod=998244353;
long long n,m,sq,cnt,sum,g[200010],w[200010];
int p[200010],pos1[200010],pos2[200010];
bool v[200010];
long long find(long long x){
    return x<sq?pos1[x]:pos2[n/x];
}
void get(int n){
    for(int i=2;i<=n;i++){
        if(!v[i])p[++cnt]=i;
        for(int j=1;j<=cnt&&i*p[j]<=n;j++){
            v[i*p[j]]=true;
            if(i%p[j]==0)break;
        }
    }
}
long long s(long long x,long long y){
    if(p[y]>=x)return 0;
    long long ret=(g[find(x)]-g[find(p[y])]+mod)%mod;
    for(int i=y+1;i<=cnt&&1ll*p[i]*p[i]<=x;i++){
        for(long long j=p[i],e=1;j<=x;j=j*p[i],e++){
            ret=(ret+1ll*(e+1)*(e+1)*(s(x/j,i)+(e>1)))%mod;
        }
    }
    return ret;
}
int main(){
    scanf("%lld",&n);
    sq=sqrt(n);
    get(sq);
    for(long long l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        w[++m]=n/l;
        sum=(sum+1ll*w[m]*(r-l+1))%mod;
        if(w[m]<sq)pos1[w[m]]=m;
        else pos2[n/w[m]]=m;
        g[m]=4ll*(w[m]-1)%mod;
    }
    for(int j=1;j<=cnt;j++){
        for(int i=1;i<=m&&1ll*p[j]*p[j]<=w[i];i++){
            g[i]=(g[i]-1ll*(g[find(w[i]/p[j])]-g[find(p[j-1])])%mod+mod)%mod;
        }
    }
    long long ans=1ll*(s(n,0)+1-sum+mod)%mod*((mod+1)>>1)%mod;
    printf("%lld\n",ans);
    return 0;
}