题解 P2257 【YY的GCD】

· · 题解

\Large\texttt{My Blog}

题目链接：Luogu 2257

求解（多组数据）

\sum\limits_{i=1}^n\sum\limits_{i=1}^m [\gcd(i,j)=\texttt{prime}]

数据范围：T=10^4，n,m\leqslant 10^7

Solution

以下所有过程中默认 n\leqslant m！

首先我们很自然想到枚举质数

\sum\limits_{p\in\texttt{prime}}\sum\limits_{i=1}^n\sum\limits_{i=1}^m [\gcd(i,j)=p]

根据套路提出 p

\sum\limits_{p\in\texttt{prime}}\sum\limits_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum\limits_{i=1}^{\left\lfloor\frac{m}{p}\right\rfloor} [\gcd(i,j)=1]

替换 \gcd 得到

\sum\limits_{p\in\texttt{prime}}\sum\limits_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum\limits_{i=1}^{\left\lfloor\frac{m}{p}\right\rfloor}\sum\limits_{d\mid \gcd(i,j)} \mu(d)

枚举 d

\sum_{d=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\mu(d)\sum\limits_{p\in\texttt{prime}}\sum\limits_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum\limits_{i=1}^{\left\lfloor\frac{m}{p}\right\rfloor} [d\mid\gcd(i,j)]

由于 x 以内 d 的倍数有 \left\lfloor\frac{x}{d}\right\rfloor 个

\sum\limits_{p\in\texttt{prime}}\sum_{d=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\mu(d)\left\lfloor\frac{n}{pd}\right\rfloor\left\lfloor\frac{m}{pd}\right\rfloor

这个式子直接求解的复杂度为 O(\texttt{质数个数}*\sqrt{n})) 的，无法通过此题！

考虑优化：令 k=pd，代入得

\sum\limits_{p\in\texttt{prime}}\sum_{d=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\mu(\frac{k}{p})\left\lfloor\frac{n}{k}\right\rfloor\left\lfloor\frac{m}{k}\right\rfloor

枚举 k

\sum\limits_{k=1}^n\sum\limits_{p\in\texttt{prime},p\mid k}\mu(\frac{k}{p})\left\lfloor\frac{n}{k}\right\rfloor\left\lfloor\frac{m}{k}\right\rfloor

设 f(x)=\sum\limits_{p\in\texttt{prime},p\mid x}\mu(\frac{x}{p}) ，询问转化为

\sum\limits_{k=1}^n f(k)\left\lfloor\frac{n}{k}\right\rfloor\left\lfloor\frac{m}{k}\right\rfloor

如果我们能求出 f 的前缀和就能解决问题了，因此考虑对线性筛！

f(x)=\sum\limits_{p\in\texttt{prime},p\mid x}\mu(\frac{x}{p})$，设 $x$ 的最小质因子为 $y$，即 $x=i\times y
  1. x\in\texttt{prime}$：显然有 $f(x)=\mu(1)=1
  2. - 当 $i$ 没有多个相同质因子时，那么当且仅当枚举的 $p=y$ 时，$\mu(\frac{x}{p})=\mu(i)$ 不为 $0$，故 $f(x)=\mu(i)
    • 当 i 也有多个相同质因子时，那么对于任何枚举的 p，都有 \mu(\frac{x}{p}) 的值都为 0，此时仍然有 \mu(\frac{x}{p})=\mu(i)，故 f(x)=\mu(i)
  3. 因为有 $f(i)=\sum\limits_{p\in\texttt{prime},p\mid i}\mu(\frac{i}{p})$，$f(x)=\sum\limits_{p\in\texttt{prime},p\mid x}\mu(\frac{i\times y}{p})

    根据 \mu 的线性筛过程，有 \mu(\frac{i\times y}{p})=-\mu(\frac{i}{p})，因此 f(i) 中的每一项能都在 f(x) 中找到对应的一项。而 x 比 i 多且仅多了一个质因子 y，因此 f(x) 比 f(i) 多了一项 \mu(\frac{i\times y}{y})=\mu(i)，故 f(x)=-f(i)+\mu(i)

综上所述，我们可以得到 f 的线性筛方程

f(x)=\begin{cases}\mu(1) & x\in\texttt{prime}\\\mu(i) & i\bmod y=0\\-f(i)+\mu(i) & i\bmod y\neq 0\end{cases}

通过求 f 的前缀和，我们可以利用整除分块通过本题！

时间复杂度：O(n+T\sqrt{n})

Code

#include <cstdio>
#include <algorithm>

const int N=1e7+5,lnN=15;
int n,m,tot,p[N/lnN],mu[N],f[N];
bool flg[N];

void init() {
    mu[1]=flg[1]=1;
    for(int i=2;i<N;++i) {
        if(!flg[i]) p[++tot]=i,mu[i]=-1,f[i]=1;
        for(int j=1;j<=tot&&i*p[j]<N;++j) {
            int x=i*p[j];
            flg[x]=1;
            if(i%p[j]==0) {
                f[x]=mu[i];
                mu[x]=0;
                break;
            } else {
                f[x]=-f[i]+mu[i];
                mu[x]=-mu[i];
            }
        }
        f[i]+=f[i-1];
    }
}
int main() {
    init();
    int T;
    for(scanf("%d",&T);T--;) {
        scanf("%d%d",&n,&m);
        long long ans=0;
        if(n>m) n^=m^=n^=m;
        for(int i=1,j;i<=n;i=j+1) {
            j=std::min(n/(n/i),m/(m/i));
            ans+=1LL*(f[j]-f[i-1])*(n/i)*(m/i);
        }
        printf("%lld\n",ans);
    }
    return 0;
}