mcfx's blog

题解、Writeup、游记和碎碎念

BZOJ 2694 & 4659 Lcm

fa(1).jpg

Solution

∑in∑jm[μ(gcd(i,j))≠0]lcm(i,j)=∑kn∣μ(k)∣∑ink∑jnk[gcd(i,j)=1]i⋅j⋅k=∑kn∣μ(k)∣⋅k∑dnkμ(d)⋅d2∑ink⋅d∑jmk⋅di⋅j=∑kn∑d[d∣k]μ(d)⋅d2⋅∣μ(kd)∣⋅pd⋅nk⋅(nk+1)2⋅mk⋅(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/ 查看。