洛谷 P3455 loj #2652 [POI2007]ZAP-Queries 题解【数学】【莫比乌斯反演】

点击量：179

莫比乌斯反演入门题？啊啊啊学了两天。

目录

题目描述

给定正整数 $ a,b,d$，找出满足以下条件的正整数对 $ (x,y)$ 的个数：

• $ 1 \le x \le a$
• $ 1 \le y \le b$
• $ \gcd(x,y)=d$

输入格式

第一行一个整数 $ n (1 \le n \le 50\ 000)$，表示询问的个数。

接下来 $ n$ 行每行三个整数 $ a,b,d,(1 \le d \le a,b \le 50\ 000)$，表示询问。

输出格式

输出 $ n$ 行，表示 $ n$ 组询问的答案。

输入输出样例

样例输入

2
4 5 2
6 4 3

样例输出

3
2

说明

第一组询问的三个正整数对分别为 $ (2,2), (2,4), (4,2)$。第二组询问的两个正整数对分别为 $ (3,3), (6,3)$。

题解：

要开始推式子了吗…

留坑：狄利克雷卷积，莫比乌斯反演。

题目要我们求
$$
\sum_{i=1}^a\sum_{j=1}^b[\gcd(i,j)=d]
$$
那么我们设
$$
f(n)=\sum_{i=1}^a\sum_{j=1}^b[\gcd(i,j)=n]
$$
构造
$$
g(n)=\sum_{n|d}f(d)
$$
因此 $ d$ 可取 $ n,2n,3n,\cdots$。

带入$ f(d)$得
$$
\begin{aligned}
g(n)&=f(n)+f(2n)+f(3n)+\cdots\\
&=\sum_{i=1}^a\sum_{j=1}^b[\gcd(i,j)=n,2n,3n,\cdots]\\
\end{aligned}
$$
发现 $ n,2n,3n,\cdots$ 都是 $ n$ 的倍数。于是可以改写成
$$
g(n)=\sum_{i=1}^a\sum_{j=1}^b[n|\gcd(i,j)]
$$
此时当且仅当 $ n|i$ 且 $ n|j$ ，考虑枚举 $ i=kn,j=kn,k\in \mathbb{N^*}$，则
$$
g(n)=\sum_{i=1}^{\left\lfloor\frac an\right\rfloor}\sum_{j=1}^{\left\lfloor\frac bn\right\rfloor}[1|\gcd(i,j)]
$$
那么由于 $ [1|\gcd(i,j)]$ 对任意 $ i,j$ 都是成立的，所以 $ g(n)=\left\lfloor\frac an\right\rfloor\left\lfloor\frac bn\right\rfloor$。

但是我们要求的是 $ f(n)$。

由
$$
g(n)=\sum_{n|d}f(d)
$$

注：当 $ d$ 很大时，$ f(d)=0$。所以不必担心上界。

根据反演知识
$$
f(n)=\sum_{n|d}\mu\left(\frac dn\right)g(d)
$$
因此
$$
f(n)=\sum_{n|d}\mu\left(\frac dn\right)\left\lfloor\frac an\right\rfloor\left\lfloor\frac bn\right\rfloor
$$
考虑枚举 $ d=in$ 中的 $ i$，$ i=\frac dn$。

则
$$
f(n)=\sum_{i=1}^{\min(a,b)/n}\mu(i)\left\lfloor\frac a{in}\right\rfloor\left\lfloor\frac b{in}\right\rfloor
$$
然后后面两个式子可以整除分块搞出来，这一段的 $ \mu(i)$ 用前缀和算出来即可。因为根据分配律，$ \left\lfloor\frac a{in}\right\rfloor\left\lfloor\frac b{in}\right\rfloor$ 相等的这一段就是 $ \left\lfloor\frac a{in}\right\rfloor\left\lfloor\frac b{in}\right\rfloor\sum_{i=1}^{\min(a,b)/n}\mu(i)$，因此只用算这一段的 $ \mu(i)$。

Code：

#include<cstdio>
#include<cstring>
int Min(int x,int y)
{return x<y?x:y;}
int pri[50100],mu[50100],cnt=0,sum[50010];
bool is[50100];
int main()
{
    memset(is,1,sizeof(is));
    is[1]=is[0]=0;
    mu[1]=1;
    for(int i=2;i<=50000;++i)
    {
        if(is[i])
        {
            pri[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&i*pri[j]<=50000;++j)
        {
            is[i*pri[j]]=0;
            if(i%pri[j])
                mu[i*pri[j]]=mu[i]*mu[pri[j]];
            else
                mu[i*pri[j]]=0;
        }
    }
    for(int i=1;i<=50000;++i)
        sum[i]=sum[i-1]+mu[i];
    int n,a,b,d;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d%d",&a,&b,&d);
        int up=Min(a,b)/d;
        long long ans=0;
        for(int i=1;i<=up;++i)
        {
            int A=a/d/i,B=b/d/i;
            int nxt=Min(up,Min(a/d/A,b/d/B));
            ans+=(long long)(sum[nxt]-sum[i-1])*A*B;
            i=nxt;
        }
        printf("%lld\n",ans);
    }
    return 0;
}