HDU 1695 – GCD

题目链接:HDU – 1695

类似题目:Luogu 2257 – YY的GCD | 题解

该题不是直接求$\sum_{i = 1}^{n} \sum_{j = 1}^{m} [(i, j) = k]$,因为$(i,j)$和$(j,i)$算同一组。

我们可以画一个$i \times j$的方格图(如下图)来容斥,我们发现只有在$i \times i$的区域内可能同时存在$(i,j)$和$(j,i)$。可以推重复的部分为

$$ \frac{(\sum_{i = 1}^{t} \sum_{j = 1}^{t} [(i,j) = k])  – x}{2} $$

其中$t = \min \{ n, m \}$,$x = [k \leq t]$。


容斥图
据此,可以知道答案为

$$ (\sum_{i = 1}^{n} \sum_{j = 1}^{m} [(i, j) = k]) – \frac{(\sum_{i = 1}^{t} \sum_{j = 1}^{t} [(i,j) = k])  – x}{2}  $$

处理$\sum_{i = 1}^{n} \sum_{j = 1}^{m} [(i, j) = k]$的方法同 Luogu 2257 – YY的GCD | 题解 。

 

说点什么

avatar
50
  Subscribe  
提醒