「Luogu 2257」YY 的 GCD

Description

题目链接:Luogu 2257

求如下式子的值:

本题 $T​$ 组数据。

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


Solution

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

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

根据套路提出 $p$

替换 $\gcd$ 得到

枚举 $d$

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

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

考虑优化:令 $k=pd$,代入得

枚举 $k$

设 $f(x)=\sum_{p\in\text{prime},p\mid x}\mu(\frac{x}{p})$ ,询问转化为

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

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

  1. $x\in\text{prime}$:显然有 $f(x)=\mu(1)=1$

  2. $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)$
  3. $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$ 的前缀和,我们可以利用数论分块通过本题!

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


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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;
}
0%