mcfx's blog

题解、Writeup、游记和碎碎念

BZOJ 2694 & 4659 Lcm

fa(1).jpg

Solution

injm[μ(gcd(i,j))0]lcm(i,j)=knμ(k)inkjnk[gcd(i,j)=1]ijk=knμ(k)kdnkμ(d)d2inkdjmkdij=knd[dk]μ(d)d2μ(kd)pdnk(nk+1)2mk(mk+1)2 \begin{align*} &\sum_i^n\sum_j^m[\mu(gcd(i,j))\neq 0]lcm(i,j)\\ =&\sum_k^n|\mu(k)|\sum_i^{\frac{n}{k}}\sum_j^{\frac{n}{k}}[gcd(i,j)=1]i\cdot j\cdot k\\ =&\sum_k^n|\mu(k)|\cdot k\sum_d^{\frac{n}{k}}\mu(d)\cdot d^2\sum_i^{\frac{n}{k\cdot d}}\sum_j^{\frac{m}{k\cdot d}}i\cdot j\\ =&\sum_k^n\sum_d[d|k]\mu(d)\cdot d^2\cdot|\mu(\frac{k}{d})|\cdot\frac{p}{d}\cdot\frac{\frac{n}{k}\cdot(\frac{n}{k}+1)}{2}\cdot\frac{\frac{m}{k}\cdot(\frac{m}{k}+1)}{2}\\ \end{align*}

最后的式子,前面是积性函数,后面根号分块。

Code

#define _GLIBCXX_IOSTREAM
#include<bits/stdc++.h>

#define N 4000001

int pri[N],pm,f[N],ps[N],pc[N];
bool np[N];

int main()
{
    for(int i=2;i<N;i++)
    {
        if(!np[i])pri[pm++]=i,f[i]=1,ps[i]=i,pc[i]=1;
        int rf;
        if(pc[i]==1)rf=f[i]*(ps[i]-ps[i]*ps[i]);
        else if(pc[i]==2)rf=-f[i]*ps[i]*ps[i]*ps[i];
        else rf=0;
        for(int j=0;i*pri[j]<N;j++)
        {
            np[i*pri[j]]=1;
            if(i%pri[j])f[i*pri[j]]=rf,ps[i*pri[j]]=pri[j],pc[i*pri[j]]=1;
            else
            {
                f[i*pri[j]]=f[i],ps[i*pri[j]]=pri[j],pc[i*pri[j]]=pc[i]+1;
                break;
            }
        }
        f[i]=rf;
    }
    f[1]=1;
    for(int i=1;i<N;i++)
        f[i]+=f[i-1];
    int T;
    for(scanf("%d",&T);T--;)
    {
        int n,m,ans=0;
        scanf("%d%d",&n,&m);
        for(int i=1,t,p,q;i<=n&&i<=m;i=t+1)
        {
            p=n/i,q=m/i,t=std::min(n/p,m/q);
            ans+=(f[t]-f[i-1])*p*(p+1)*q*(q+1)>>2;
        }
        printf("%d\n",ans&0x3fffffff);
    }
}

日期: 2017-02-28

标签: BZOJ 莫比乌斯反演

这是一篇旧文,原始文章及评论可在 https://oldblog.mcfx.us/archives/181/ 查看。