← 返回题目列表

Codeforces · 1541/B

B. 愉快的对

中文机器翻译题面 查看原题

给定一个数组 $$$a_1, a_2, \dots, a_n$$$,由 $$$n$$$ 不同的整数组成。计算满足 $$$i < j$$$ 且 $$$a_i \cdot a_j = i + j$$$ 的索引对 $$$(i, j)$$$ 的数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 案例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2 \cdot n$$$) - 数组 $$$a$$$。保证所有元素都是不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出索引对 $$$(i, j)$$$ 的数量,使得 $$$i < j$$$ 且 $$$a_i \cdot a_j = i + j$$$。

示例

输入 #1

3
2
3 1
3
6 1 5
5
3 1 5 9 2

输出 #1

1
1
3

注意

对于第一个测试用例,唯一满足约束的对是 $$$(1, 2)$$$,如 $$$a_1 \cdot a_2 = 1 + 2 = 3$$$

对于第二个测试用例,唯一满足约束的对是 $$$(2, 3)$$$。

对于第三个测试用例,满足约束的对是 $$$(1, 2)$$$、$$$(1, 5)$$$ 和 $$$(2, 3)$$$。