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

作者: wjyyy 分类: 数学,莫比乌斯反演,解题报告 发布时间: 2019-02-17 22:28

点击量:42

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

题目描述

给定正整数 \(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;
}

说点什么

avatar
  Subscribe  
提醒
/* */