Luogu 2522 – 「HAOI2011」Problem b

题目链接:Luogu 2522

题目给出$T$组$(a,b,c,d,k)$,每次询问:

$$\sum_{x = a}^{b} \sum_{y = c}^{d} [(x,y) = k]$$

思路:考虑简化的问题

$$ \begin{aligned} & \sum_{x = 1}^{n} \sum_{y = 1}^{m} [(x,y) = k] \\ = & \sum_{x = 1}^{ \lfloor \frac{n}{k} \rfloor } \sum_{y = 1}^{ \lfloor \frac{m}{k} \rfloor } [(x,y) = 1]  \\ = & \sum_{x = 1}^{ \lfloor \frac{n}{k} \rfloor } \sum_{y = 1}^{ \lfloor \frac{m}{k} \rfloor } \sum_{d|x, d|y} \mu(d)  \\  = & \sum_{d = 1}^{\min \{ \lfloor \frac{n}{k} \rfloor , \lfloor \frac{m}{k} \rfloor \}} \mu(d)  \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor  \end{aligned} $$

令$u =\lfloor \frac{n}{k} \rfloor$,$v =\lfloor \frac{m}{k} \rfloor  $,则上式可以表示为

$$ \sum_{d = 1}^{\min \{ u, v \} } \mu(d)  \lfloor \frac{u}{d} \rfloor \lfloor \frac{v}{d} \rfloor $$

设$f(u, v) =\sum_{d = 1}^{\min \{ u, v \} } \mu(d)  \lfloor \frac{u}{d} \rfloor \lfloor \frac{v}{d} \rfloor$,预处理$\mu(d)$的前缀和,然后整除分块可以在$O(\sqrt{u} + \sqrt{v})$的时间内求出$f(u,v)$。

那么根据容斥原理(对二维前缀和进行容斥),原题答案可以表示为

$$ f(\lfloor \frac{b}{k} \rfloor,\lfloor \frac{d}{k} \rfloor) – f(\lfloor \frac{b}{k} \rfloor,\lfloor \frac{c – 1}{k} \rfloor) -f(\lfloor \frac{a – 1}{k} \rfloor,\lfloor \frac{d}{k} \rfloor) +f(\lfloor \frac{a – 1}{k} \rfloor,\lfloor \frac{c – 1}{k} \rfloor)$$

 

 

说点什么

avatar
50
  Subscribe  
提醒