Luogu 2257 – YY的GCD

题目链接:Luogu 2257

题目要求对于$1 \leq i \leq n$,$1 \leq j \leq m$,满足${\rm gcd}(i,j)$为素数的$(i,j)$对数。

首先先考虑一个简化版的问题:求满足${\rm gcd} (i,j)=1$即$i$和$j$互质的对数。这个问题就是让我们求

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

这里的$[{\rm gcd} (i,j) = 1]$ 可以看作是单位函数 $\epsilon ({\rm gcd} (i,j))$,根据Direchlet卷积性质$\epsilon = 1 * \mu$,故

$$ [{\rm gcd} (i,j) = 1] = (\mu * 1)({\rm gcd} (i,j)) = \sum_{d |{\rm gcd} (i,j)} \mu (d) =\sum_{d | i, d | j} \mu (d) $$

所以上式可以写为

$$\sum_{i = 1}^{n} \sum_{j = 1}^{m} [{\rm gcd} (i, j) = 1] = \sum_{i = 1}^{n} \sum_{j = 1}^{m}\sum_{d | i, d | j} \mu (d) $$

交换求和顺序,得到

$$ \sum_{i = 1}^{n} \sum_{j = 1}^{m} [{\rm gcd} (i, j) = 1] = \sum_{d = 1} ^ {\min(n, m)} \mu(d) \lfloor \frac{n}{d} \rfloor \lfloor\frac{m}{d} \rfloor $$

接着这这个问题就可以对$\mu(d)$求前缀和然后整除分块解决。

回归到原问题。其实我们要求的就是这个问题($P$为素数集合):

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

同样地,我们先做一些,${\rm gcd}(i,j) = p$变换成${\rm} gcd(\frac{i}{p}, \frac{j}{p}) = 1$,转化为第一个问题,然后再类似地调换求和顺序:

$$\begin{aligned} \sum_{p \in P} \sum_{i = 1}^{n} \sum_{j = 1}^{m} [{\rm gcd} (i,j) = p] = &  \sum_{p \in P} \sum_{i = 1}^{\lfloor \frac{n}{p} \rfloor} \sum_{i = 1}^{\lfloor \frac{m}{p} \rfloor}[{\rm gcd}(i, j)= 1] \\ = & \sum_{p \in P} \sum_{i = 1}^{\lfloor \frac{n}{p} \rfloor} \sum_{i = 1}^{\lfloor \frac{m}{p} \rfloor} \sum_{d | i, d | j} \mu(d) \\ = & \sum_{p \in P} \sum_{d = 1} ^ {\min (\lfloor \frac{n}{p} \rfloor,\lfloor \frac{m}{p} \rfloor)}  \mu(d) \lfloor \frac{n}{pd} \rfloor \lfloor\frac{m}{pd} \rfloor  \end{aligned} $$

令$t = pd$,则上式可以化为

$$ \sum_{p \in P} \sum_{t = 1} ^ {\min (n,m)} \mu (\frac{t}{p}) \lfloor \frac{n}{t} \rfloor \lfloor\frac{m}{t} \rfloor  $$

交换求和次序得到上式等于

$$ \sum_{t = 1} ^ {\min (n,m)} \lfloor \frac{n}{t} \rfloor \lfloor\frac{m}{t} \rfloor \sum_{p\in P, p | t} \mu (\frac{t}{p})  $$

取$g(t) =\sum_{p\in P, p | t} \mu (\frac{t}{p}) $,则上式为

$$ \sum_{t = 1} ^ {\min (n,m)} \lfloor \frac{n}{t} \rfloor \lfloor\frac{m}{t} \rfloor g(t)  $$

这就变成了一个简单的整除分块问题——预处理$g(t)$的前缀和然后枚举$\lfloor \frac{n}{t} \rfloor$和$\lfloor \frac{m}{t} \rfloor$的取值。

那么下面问题是如何求$g(t)$,我们知道

$$ g(t) =\sum_{p\in P, p | t} \mu (\frac{t}{p}) $$

可以使用埃氏筛求$g(t)$,直接枚举素数的倍数算贡献,具体可以看代码实现。

这里筛法的复杂度为$O(n \log \log n)$,询问的复杂度为$O(\sqrt{n})$。

 

1
说点什么

avatar
50
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] Luogu 2257 – YY的GCD […]