Description

给出 $n$ 个询问,每次询问有多少个数对 $(x,y)$ 满足 $a\leq x\leq b, c\leq y \leq d$,且 $gcd(x,y)=k$。

Idea

首先我们可以差分一下,求下面这个函数的值。

$$f(k)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=k]$$

我们设

$$F(k)=\sum\limits_{k|d}f(d)(d<=\min(n,m))$$

表示所有公约数为 $k$ 的倍数 $d$ 的答案个数。

根据莫比乌斯反演,

$$f(k)=\sum\limits_{k|d}\mu(\lfloor\frac{d}{k}\rfloor)F(d)$$

枚举 $x=\lfloor\frac{d}{k}\rfloor$,化为

$$\begin{aligned}f(k)=&\sum\limits_{x=1}^{\min(\frac{n}{k},\frac{m}{k})}\mu(x)F(xk) \\ =& \sum\limits_{x=1}^{\min(\frac{n}{k},\frac{m}{k})}\mu(x) \lfloor\frac{n}{xk}\rfloor\lfloor\frac{m}{xk}\rfloor\end{aligned}$$

对 $\mu(x)$ 求前缀和,分块处理即可。

Code