[POI2007]ZAP-Queries - 莫比乌斯反演

[POI2007] ZAP-Queries

对于给定的整数 \(a,b\) 和 \(d\) ，有多少正整数对 \(x,y\) ，满足 \(x \le a，y \le b\)，并且 \(gcd(x,y)=d\) 。

利用Mobius函数性质求解

根据题意

\[ans=\sum_{i=1}^a \sum_{j=1}^b [{gcd(i,j)=d}]\]

\[ans=\sum_{i=1}^{a/d} \sum_{j=1}^{b/d}[gcd(i,j)=1]\]

这里可以直接根据Mobius函数的性质，有

\[ans=\sum_{i=1}^{a/d} \sum_{j=1}^{b/d} \sum_{p|gcd(i,j)}\mu(p)\]

换一个变量枚举,把最后一个求和提到前面,范围 \(min(a/d,b/d)\) ，那么

\[ans=\sum_{p=1}^{min(a/d,b/d)}{ \left({\mu(p)} \sum_{i=1}^{a/d} \sum_{j=1}^{b/d} \lfloor\frac{a}{p d} \rfloor \lfloor\frac{b}{p d}\rfloor\right)}\]

对上式稍作说明，令 \(x=a/d,y=b/d\) ，
\(p\) 是 \(x,y\) 的一个因子,在 \(x\) 的范围内有 \(\lfloor\frac{x}{p}\rfloor\) 个 \(p\) 的倍数,对于 \(y\) 同理,所以每个因子 \(p\) 都有 \(\lfloor\frac{x}{p}\rfloor\lfloor\frac{y}{p}\rfloor\) 的贡献

可以使用整除分块优化到 \(O(\sqrt n)\)

利用Mobius反演求解

首先，我们可以定义 \(f(d)\) 和 \(F(d)\) 如下：

\[f(d)=\sum_{i=1}^N\sum_{j=1}^M[gcd(i,j)=d]\]

\[F(d)=\sum_{i=1}^N\sum_{j=1}^M[d|gcd(i,j)]\]

发现

\[\sum_{n|d}f(d)=F(n)=\lfloor\frac Nn\rfloor\lfloor\frac Mn\rfloor\]

莫比乌斯反演，得到：

\[f(n)=\sum_{n|d}\mu(\lfloor\frac dn\rfloor)F(d)\]

于是
\[ans=f(d)=\sum_{d|p}\mu(\lfloor\frac pd\rfloor)F(p)\]

换个元
\[ans=\sum_{p'}\mu(p')F( p' d ) =\sum_{p'=1}^{min(\lfloor\frac Nd\rfloor,\lfloor\frac Md\rfloor)}\mu(p')\lfloor\frac N{p'd}\rfloor \lfloor \frac M{p'd}\rfloor\]

把 \(p'\) 写作 \(p\) ，得到

\[ans=\sum_{p}\mu(p)F( p d ) =\sum_{p=1}^{min(\lfloor\frac Nd\rfloor,\lfloor\frac Md\rfloor)}\mu(p)\lfloor\frac N{pd}\rfloor \lfloor \frac M{pd}\rfloor\]

后续求解方法与上一种相同。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 50005;

int pr[N],is[N],mu[N],cnt;

signed main() {
    mu[0]=mu[1]=1; is[1]=1;
    for(int i=2;i<=N;i++) {
        if(is[i]==0) {
            pr[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1; j<=cnt&&pr[j]*i<N; ++j) {
            is[pr[j]*i]=1;
            if(i%pr[j]==0) {
                mu[pr[j]*i]=0;
                break;
            }
            else {
                mu[pr[j]*i]=-mu[i];
            }
        }
    }
    for(int i=1;i<=N;i++) mu[i]+=mu[i-1];
    int T;
    cin>>T;
    while(T--) {
        int n,m,d;
        cin>>n>>m>>d;
        n/=d; m/=d;
        long long ans=0;
        for(int l=1,r;l<=min(n,m);l=r+1) {
            r=min(n/(n/l),m/(m/l));
            ans+=(n/l)*(m/l)*(mu[r]-mu[l-1]);
        }
        cout<<ans<<endl;
    }
}

[POI2007]ZAP-Queries - 莫比乌斯反演

原文：https://www.cnblogs.com/mollnn/p/11660842.html