化成数学代数式就是这样：
$$\sum_{x=a}^b\sum_{y=c}^d[\gcd(x,y)=k]$$
根据差分的思想，可以将该式变成：
$$\sum_{x=1}^b\sum_{y=1}^d[\gcd(x,y)=k]-\sum_{x=1}^{a-1}\sum_{y=1}^d[\gcd(x,y)=k]-\sum_{x=1}^b\sum_{y=1}^{c-1}[\gcd(x,y)=k]+\sum_{x=1}^{a-1}\sum_{y=1}^{b-1}[\gcd(x,y)=k]$$
只要求出：
$$\sum_{i=1}^N\sum_{j=1}^M[\gcd(i,j)=k]$$
最后的答案就能求解。
我们来推导这个式子：
$$\begin{array}{ll} &\sum\limits_{i=1}^N\sum\limits_{j=1}^M[\gcd(i,j)=k]\\=&\sum\limits_{i=1}^{\lfloor\frac Nk\rfloor}\sum\limits_{j=1}^{\lfloor\frac Mk\rfloor}[\gcd(i,j)=1]\\ =&\sum\limits_{i=1}^{\lfloor\frac Nk\rfloor}\sum\limits_{j=1}^{\lfloor\frac Mk\rfloor}\epsilon(\gcd(i,j)) & \text{根据单位函数?的定义}\\=&\sum\limits_{i=1}^{\lfloor\frac Nk\rfloor}\sum\limits_{j=1}^{\lfloor\frac Mk\rfloor}\sum\limits_{d|gcd(i,j)}\mu(d)&\text{注意这一步的变换是根据} \epsilon=\mu*1 \text{得来的}\\=&\sum\limits_{d=1}^{\min(N,M)}\mu(d)\sum\limits_{d|i,i\leq \lfloor\frac Nk\rfloor}\sum\limits_{d|j,j\leq \lfloor\frac Mk\rfloor}&\text{调换求和顺序} \\=&\sum\limits_{d=1}^{\min(N,M)}\mu(d) \lfloor \frac{\lfloor \frac Nk \rfloor}d \rfloor \lfloor \frac{\lfloor \frac Mk \rfloor}d \rfloor \end{array}$$
原文：https://www.cnblogs.com/ac-evil/p/10372298.html