acm-(数论、好题、莫比乌斯反演、推式子)51nod 1222 最小公倍数计数

传送门 设$f(n)={\sum }_{i=1}^n{\sum }_{j=1}^n[lcm(i,j)\le n]$，题目让我们求的其实是${\sum }_{i=1}^b{\sum }_{j=1}^i[lcm(i,j)\le b]-{\sum }_{i=1}^{a-1}{\sum }_{j=1}^i[lcm(i,j)\le a-1]$，也就是说要求出${\sum }_{i=1}^n{\sum }_{j=1}^i[lcm(i,j)\le b]$，但这个式子不太方便我们反演，它其实就是$\frac{1}{2}({\sum }_{i=1}^n{\sum }_{j=1}^n[lcm(i,j)\le n]+{\sum }_{i=1}^n[lcm(i,i)\le n])=\frac{f(n)+n}{2}$，因此我们下面考虑如何求出$f(n)$。

$\begin{array}{rl}f(n)& =\sum _{i=1}^n\sum _{j=1}^n[lcm(i,j)\le n]\\ & =\sum _{k=1}^n\sum _{i=1}^n\sum _{j=1}^n[\frac{ij}{k}\le n][gcd(i,j)=k]\\ & =\sum _{k=1}^n\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{n}{k}\rfloor }[ijk\le n]\sum _{d\mid i,d\mid j}\mu (d)\\ & =\sum _{k=1}^n\sum _{i=1}^n\sum _{j=1}^n[ijk\le n]\sum _{d\mid i,d\mid j}\mu (d)\\ & =\sum _{d=1}^n\mu (d)\sum _{k=1}^n\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{j=1}^{\lfloor \frac{n}{d}\rfloor }[ijk\le \lfloor \frac{n}{d^2}\rfloor ]\\ & =\sum _{d=1}^{\lfloor \sqrt{n}\rfloor }\mu (d)\sum _{k=1}^{\lfloor \frac{n}{d^2}\rfloor }\sum _{i=1}^{\lfloor \frac{n}{d^2}\rfloor }\sum _{j=1}^{\lfloor \frac{n}{d^2}\rfloor }[ijk\le \lfloor \frac{n}{d^2}\rfloor ]\\ & =\sum _{d=1}^{\lfloor \sqrt{n}\rfloor }\mu (d)g(\lfloor \frac{n}{d^2}\rfloor ).....令g(n)=\sum _{k=1}^n\sum _{i=1}^n\sum _{j=1}^n[ijk\le n]\end{array}$ 现在考虑如何求$g(n)$，根据对称性，我们假设$k\le i\le j$，于是容易确定$k\in [1,\lfloor n^{\frac{1}{3}}\rfloor ],i\in [k,\lfloor \sqrt{\frac{n}{k}}\rfloor ],j\in [i,\lfloor \frac{n}{ik}\rfloor ]$，枚举量大概是$O(\sqrt{n}+\sqrt{\frac{n}{2}}+\sqrt{\frac{n}{3}}+...+\sqrt{\frac{n}{n^{\frac{1}{3}}}})=O({\int }_1^{n^{\frac{1}{3}}}\sqrt{\frac{n}{x}}\mathrm{d}x)=O(n^{\frac{2}{3}})$，然后枚举的时候分三种情况计算贡献即可$k<i<j$时要算6，$k=i<j或k<i=j$时要算3，$k=i=j$时要算1。

总复杂度的话就是$O({\sum }_{d=1}^{\sqrt{n}}{(\frac{n}{d^2})}^{\frac{2}{3}})=O(n^{\frac{2}{3}})$，你可以理解为杜教筛外面套了个$O(\sqrt{n})$的分块，因此复杂度不变。

int prim[maxn],tot,mu[maxn]; bool flag[maxn]; void init(int n){ mu[1]=1; FOR(i,2,n+1){ if(!flag[i])prim[tot++]=i,mu[i]=-1; for(register int j=0;j<tot && prim[j]*i<=n;++j){ flag[i*prim[j]]=1; if(i%prim[j]==0)break; mu[i*prim[j]]=-mu[i]; } } } ll get(ll n){ register int limt1 = pow(n,1.0/3.0),limt2; register ll ans=0,c,up; while(1ll*limt1*limt1*limt1<=n)limt1++; while(1ll*limt1*limt1*limt1>n)limt1--; FOR(k,1,limt1+1){ c=n/k; limt2=(int)(sqrt(c)+0.5); FOR(i,k,limt2+1){ up=c/i; if(up<i)break; if(i==k){ ans+=3ll*(up-i)+1ll; }else{ ans+=6ll*(up-i)+3ll; } } } return ans; } ll cal(ll n){ if(!n)return 0; register int limt = sqrt(n); register ll ans=0; FOR(i,1,limt+1)ans+=mu[i]*get(n/(1ll*i*i)); return (ans+n)>>1; } int main(){ ll a,b; rd(&a,&b); init((int)sqrt(b)); wrn(cal(b)-cal(a-1)); }