神奇脑洞题解——[HAOI2011]Problem b

[HAOI2011]Problem b

一句话题面：

求：

$\sum_{i=a}^{b}\sum_{j=c}^{d}gcd(i,j)=k$

首先对问题进行简化：

$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)=k$

这实际上就是POI2007ZAP—Queries

设：

$f(k)=\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)=k$

$F(k)=\sum_{i=1}^{n}\sum_{j=1}^{m}(k|gcd(i,j))$

则可以发现

$F(k)=\sum_{k|d}f(d)$

且：

$F(k)=\sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{k} \right \rfloor}(1|gcd(i,j))=\left \lfloor \frac{n}{k} \right \rfloor*\left \lfloor \frac{m}{k} \right \rfloor$

进行莫比乌斯反演

$f(k)=\sum_{k|d}F(d)\mu(\frac{d}{k})$

设

$T=\frac{d}{k}$

则有：

$f(k)=\sum_{T=1}^{\left \lfloor \frac{min(n,m)}{k} \right \rfloor}\mu(T)F(Tk)=\sum_{T=1}^{\left \lfloor \frac{min(n,m)}{k} \right \rfloor}\mu(T)\left \lfloor \frac{n}{Tk} \right \rfloor\left \lfloor \frac{m}{Tk} \right \rfloor$

则对于简化问题有答案公式如上

由于后半部分(F(Tk))可以进行整除分块，因此总体时间复杂度为(√n)

回到实际问题：

考虑上述式子的意义：在i：1—n，j：1——n时gcd(i,j)=k的数对个数

显然发现可以容斥：

记：Solve(n,m)= $f(k)=\sum_{T=1}^{\left \lfloor \frac{min(n,m)}{k} \right \rfloor}\mu(T)F(Tk)=\sum_{T=1}^{\left \lfloor \frac{min(n,m)}{k} \right \rfloor}\mu(T)\left \lfloor \frac{n}{Tk} \right \rfloor\left \lfloor \frac{m}{Tk} \right \rfloor$

则最终答案即Solve(b,d)-Solve(b,c-1)-Solve(a-1,d)+Solve(a-1,c-1)

代码如下：

#include<iostream>
#include<cstdio>
#define int long long int
using namespace std;
int miu[50001],vis[50001],pri[50001];
int a,b,c,d,k,t,cnt;
void Euler()
{
    miu[1]=1;
    for(int i=2;i<=50000;i++)
    {
        if(!vis[i])
        {
            ++cnt;
            pri[cnt]=i;
            miu[i]=-1;
        }
        for(int j=1;j<=cnt;j++)
        {
            if(pri[j]*i>50000)
                break;
            if(i%pri[j]==0)
            {
                vis[i*pri[j]]=1;
                miu[i*pri[j]]=0;
                break;
            }
            else
            {
                vis[i*pri[j]]=1;
                miu[i*pri[j]]=-miu[i];
            }
        }
    }
    for(int i=1;i<=50000;i++)
    {
        miu[i]+=miu[i-1];
    }
}
int Work(int n,int m)
{
    if(n>m)
        swap(n,m);
    int X=n/k,ans=0;
    for(int l=1,r;l<=X;l=r+1)
    {
        r=min(n/(n/l),m/(m/l));
        ans+=(miu[r]-miu[l-1])*(n/(l*k))*(m/(l*k));
    }
    return ans;
}
signed main()
{
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    scanf("%lld",&t);
    Euler();
    while(t--)
    {
        scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k);
        printf("%lld
",Work(b,d)-Work(a-1,d)-Work(b,c-1)+Work(a-1,c-1));
    }
    return 0;
}

完结撒花！！！