acm-(数论、莫比乌斯反演、杜教筛)51nod 1238 最小公倍数之和 V3

传送门 先常规反演得到$ans={\sum }_{i=1}^n\frac{1}{4}[\lfloor \frac{n}{i}\rfloor (\lfloor \frac{n}{i}\rfloor +1){]}^{2}f(i)$，其中$f(n)=n{\sum }_{d\mid n}d\mu (d)$。 考虑如何计算$f$的前缀和，由于$f(n)=n{\sum }_{d\mid n}d\mu (d)={\sum }_{d\mid n}\mu (d)d^2\frac{n}{d}=((\mu \cdot i{d}_2)\ast id)(n)$，故我们可以设$g=f\ast i{d}_2=(\mu \cdot i{d}_2)\ast id\ast i{d}_2=((\mu \cdot i{d}_2)\ast i{d}_2)\ast id=ϵ\ast id=id$，然后就是杜教筛的套路式了，设$S(n)={\sum }_{i=1}^{n}f(i)$，于是有$S(n)={\sum }_{i=1}^{n}id(i)-{\sum }_{i=2}^{n}i{d}_2(i)S(\lfloor \frac{n}{i}\rfloor )$。

由于杜教筛外面套分块不会影响杜教筛复杂度(我也不知道为什么)，因此总复杂度仍然为$O(n^{\frac{2}{3}})$，注意别忘了预处理前$n^{\frac{2}{3}}$的$f$的前缀和。

ll n; int N,limt,prim[maxn],tot,s[maxn],dp[maxm]; bool flag[maxn]; int id(ll x){ return x<=limt?x:n/x+limt; } void init(int n){ s[1]=1; FOR(i,2,n+1){ if(!flag[i])prim[tot++]=i,s[i]=1+mod-i; for(register int j =0;j<tot && prim[j]*i<=n;++j){ flag[i*prim[j]]=1; if(i%prim[j]==0){ s[i*prim[j]]=s[i]; break; } s[i*prim[j]]=1ll*s[i]*(1+mod-prim[j])%mod; } } FOR(i,1,n+1){ s[i]=1ll*s[i]*i%mod; add(s[i],s[i-1]); } } int S(ll n){ if(n<=N)return s[n]; register int idd =id(n),ans,pre=1,cur=0; if(dp[idd])return dp[idd]; register ll i=2,j;ans=sm1(n%mod); while(i<=n){ j=n/(n/i); dec(ans,1ll*((cur=sm2(j%mod))-pre+mod)*S(n/i)%mod); i=j+1; pre=cur; } return dp[idd]=ans; } int main(){ rd(&n); N=pow(n,2.0/3.0); init(N=max(N,10000)); register ll i=1,j; register int pre=0,ans=0,cur=0; while(i<=n){ j=n/(n/i); add(ans,1ll*sm3(n/i%mod)*((cur=S(j))-pre+mod)%mod); i=j+1; pre=cur; } wrn(ans); }