P2522 [HAOI2011]Problem b （莫比乌斯反演）

P2522 [HAOI2011]Problem b

题意：

n个询问，在$a\le x\le b,c\le y\le d$范围内，满足gcd(x,y)=k的数对有多少个。

Solution:

反演过程

法一：

$$\begin{gathered} \sum _{x=a}^b\sum _{y=c}^d[gcd(x,y)=k] \\ =\sum _{x=a}^b\sum _{y=c}^d\sum _{k|gcd(x,y)}[gcd(\frac{x}{k},\frac{y}{k})=1] \\ =\sum _{x=\lceil \frac{a}{k}\rceil }^{\lfloor \frac{b}{k}\rfloor }\sum _{y=\lceil \frac{c}{k}\rceil }^{\lfloor \frac{d}{k}\rfloor }[gcd(x,y)=1] \\ =\sum _{x=\lceil \frac{a}{k}\rceil }^{\lfloor \frac{b}{k}\rfloor }\sum _{y=\lceil \frac{c}{k}\rceil }^{\lfloor \frac{d}{k}\rfloor }\sum _{d_1|gcd(x,y)}\mu (d_1) \\ =\sum _{d_1=1}^{min(b,d)}\mu (d_1)\sum _{x=\lceil \frac{a}{k}\rceil }^{\lfloor \frac{b}{k}\rfloor }\sum _{y=\lceil \frac{c}{k}\rceil }^{\lfloor \frac{d}{k}\rfloor }1 \\ =\sum _{d_1=1}^{min(b,d)}\mu (d_1)(\lfloor \frac{b}{k{d}_1}\rfloor -\lceil \frac{a}{k{d}_1}\rceil +1)(\lfloor \frac{d}{k{d}_1}\rfloor -\lceil \frac{c}{k{d}_1}\rceil +1) \end{gathered}$$

法二：

由通用的反演式子$F(n)={\sum }_{n|d}f(d),f(n)={\sum }_{n|d}\mu (\frac{d}{n})F(d)$推出

设$f(k)={\sum }_{x=a}^b{\sum }_{y=c}^d[gcd(x,y)=k]$
那么
$$\begin{gathered} F(n)=\sum _{n|k}f(k) \\ =\sum _{n|k}\sum _{x=a}^b\sum _{y=c}^d[gcd(x,y)=k] \\ =\sum _{x=a}^b\sum _{y=c}^d[n|gcd(x,y)] \\ =(\lfloor \frac{b}{n}\rfloor -\lceil \frac{a}{n}\rceil +1)(\lfloor \frac{d}{n}\rfloor -\lceil \frac{c}{n}\rceil +1) \end{gathered}$$
反过来推出（对后面的式子中有个说明n=d1*k）
$$\begin{gathered} f(k)=\sum _{k|n}\mu (\frac{n}{k})F(n) \\ =\sum _{k|n}\mu (\frac{n}{k})(\lfloor \frac{b}{n}\rfloor -\lceil \frac{a}{n}\rceil +1)(\lfloor \frac{d}{n}\rfloor -\lceil \frac{c}{n}\rceil +1) \\ =\sum _{d_1=1}^{min(\frac{b}{k},\frac{d}{k})}\mu (d_1)(\lfloor \frac{b}{k{d}_1}\rfloor -\lceil \frac{a}{k{d}_1}\rceil +1)(\lfloor \frac{d}{k{d}_1}\rfloor -\lceil \frac{c}{k{d}_1}\rceil +1) \end{gathered}$$

到这里，反演的式子也就推出来了。但是，你不会以为到这里就结束了吧。不会吧！不会吧！
当你把代码写出来，然后提交，惊喜的发现WA了（可达鸭眉头一皱，发现事情并不简单）。
若是暴力的去跑这个反演式子，你就会发现复杂度并不够优秀，TLE了，因此要对这个过程进行优化，通过分块优化这个过程。
但是只是套上一个分块，并对$\mu$进行前缀求和是不够的。
要发现前缀求和的这个特点
$$\begin{gathered} \sum _{i=a}^b\sum _{j=c}^d(...) \\ =\sum _{i=1}^b\sum _{j=c}^d(...)-\sum _{i=1}^{a-1}\sum _{j=c}^d(...) \\ =\sum _{i=1}^b\sum _{j=1}^d(...)-\sum _{i=1}^b\sum _{j=1}^{c-1}(...)-(\sum _{i=1}^{a-1}\sum _{j=1}^d(...)-\sum _{i=1}^{a-1}\sum _{j=1}^{c-1}(...)) \\ =\sum _{i=1}^b\sum _{j=1}^d(...)-\sum _{i=1}^b\sum _{j=1}^{c-1}(...)-\sum _{i=1}^{a-1}\sum _{j=1}^d(...)+\sum _{i=1}^{a-1}\sum _{j=1}^{c-1}(...) \end{gathered}$$
以上推演过程过于复杂，容易出错，所以一般将[a,b]的范围变成[1,b]-[1,a-1]，这样就不用弄清楚上下界取整的情况。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
int mu[50005];
int vis[50005];
int prime[50005],cnt=0;
int pre[50005];
void initMul()
{
   
    mu[1]=1;
    for(int i=2;i<=50000;i++)
    {
   
        if(!vis[i])
        {
   
            mu[i]=-1;
            prime[cnt++]=i;
        }
        for(int j=0;j<cnt&&1ll*i*prime[j]<=50000;j++)
        {
   
            vis[i*prime[j]]=1;
            if(i%prime[j])mu[i*prime[j]]=-mu[i];
            else {
   mu[i*prime[j]]=0;break;}
        }
    }
    for(int i=1;i<=50000;i++)pre[i]=pre[i-1]+mu[i];
}
ll calc(int a,int b)
{
   
    ll res=0;
    int M=min(a,b);
    for(int l=1,r;l<=M;l=r+1)
    {
   
        r=min(a/(a/l),b/(b/l));
        res+=1ll*(pre[r]-pre[l-1])*(a/l)*(b/l);
    }
    return res;
}
int main()
{
   
    initMul();
    int n;scanf("%d",&n);
    while(n--)
    {
   
        int a,b,c,d,k;
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        ll res=calc(b/k,d/k)-calc(b/k,(c-1)/k)-calc((a-1)/k,d/k)+calc((a-1)/k,(c-1)/k);
        printf("%lld\n",res);
    }
    return 0;
}