「Luogu 2257」YY 的 GCD

Description

题目链接：Luogu 2257

求如下式子的值：

$\sum_{i=1}^n\sum_{i=1}^m [\gcd(i,j)=\text{prime}]$

本题 $T$ 组数据。

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

Solution

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

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

$\sum_{p\in\text{prime}}\sum_{i=1}^n\sum_{i=1}^m [\gcd(i,j)=p]$

根据套路提出 $p$

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

替换 $\gcd$ 得到

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

枚举 $d$

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

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

$\sum_{p\in\text{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(\text{质数个数}*\sqrt{n}))$ 的，无法通过此题！

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

$\sum_{p\in\text{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_{k=1}^n\sum_{p\in\text{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_{p\in\text{prime},p\mid x}\mu(\frac{x}{p})$ ，询问转化为

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

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

$f(x)=\sum_{p\in\text{prime},p\mid x}\mu(\frac{x}{p})$，设 $x$ 的最小质因子为 $y$，即 $x=i\times y$

$x\in\text{prime}$：显然有 $f(x)=\mu(1)=1$
$i\bmod y=0$，即 $x$ 有多个最小质因子：
- 当 $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)$
$i\bmod y\neq 0$，即 $x$ 有一个最小质因子：

因为有 $f(i)=\sum_{p\in\text{prime},p\mid i}\mu(\frac{i}{p})$，$f(x)=\sum_{p\in\text{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\text{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;
}