Editorial

---

D

summary:

$a_i, b_i(1 \leq a_i,b_i \leq n)$인 쌍이 $n$개 주어지는데, $a_i a_j = b_i+b_j(i<j)$인 $(i,j)$쌍이 몇개인지 구하는 문제이다.

solution:

$b_i+b_j \leq 2n $ 이므로 $a_i a_j \leq 2n$이다. (그렇지 않은 것은 셀 필요가 없다)

따라서 $min(a_i,a_j)\leq 2n$이다.

$lim=\sqrt{2n}$

$cnt[a_i][b_i]$: $a_i \leq \sqrt{2n}$인 $(a_i,b_i)$ 쌍의 개수라고 하자.

$a_i=a_j$인 $(i,j)$쌍의 개수는 다음과 같다.

${\sum_{i=1}^{n} cnt[a_i][a_i^2-b_i] - \sum_{i=1}^{lim}{cnt[i][{i^2 \over {2}}]}}\over 2$이다.

$\sum_{i=1}^{lim}{cnt[i][{i^2 \over 2}]}$는 예를 들면 $(2,2)$가 여러개 있을 때처럼 같은 쌍끼리 $a_i a_j =b_i+b_j$가 되는 경우이다.

$a_j\leq a_i$인 경우는 다음과 같다.

$\sum_{i=1}^{n} \sum_{j=1}^{min(a_i-1,{2n \over a_i})} cnt[j][j a_i - b_i]$

시간 복잡도는 $O(n \sqrt{n})$이고, 공간 복잡도도 동일하다.