2196B: Another Problem about Beautiful Pairs

brute force, math, two pointers, 1600, https://codeforces.com/problemset/problem/2196/B

In the array 𝑎, we call a pair of indices 𝑖, 𝑗 beautiful if the following condition holds:

𝑎𝑖⋅𝑎𝑗=𝑗−𝑖.

Count the number of beautiful pairs in the array 𝑎.

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤10^4). The description of the test cases follows.

The first line of each test case contains a single integer 𝑛 (2≤𝑛≤2⋅10^5).

The second line of each test case contains 𝑛 integers 𝑎𝑖 (1≤𝑎𝑖≤10^9).

Additional constraints on the input:

The sum of 𝑛 across all test cases does not exceed 2⋅10^5.

Output

For each test case, output a single integer — the answer to the problem.

Example

input

4
5
1 1 2 100 4
6
2 2 1 1 2 2
10
1 1 2 3 4 1 1 7 3 9
2
1000000000 1000000000

output

Note

In the first example, there are 3 beautiful pairs: (1,2), (1,3), and (1,5).

In the second example, there are 7 beautiful pairs: (1,3), (1,5), (2,4), (2,6), (3,4), (3,5), and (4,6).

【汤立祥 25物理学院】思路：这道神秘的题目我一开始以为是在写一个 $O (n^{2})$ 的算法之后使用猛烈的剪枝让它过样例的，在尽力之后过了16/29个样例才TLE。核心思想如下：对于 $a [i]$ ，如果想要找到与之能组成 Beautiful Pair 的对，那么我们需要搜索引索 $j = i + k \cdot a [i]$ ，因此我们至多只需要遍历 $⌈ \frac{n}{a [i]} ⌉$ 个数据点。当 $a [i]$ 足够大时，这样子的遍历的确能省掉很多空间，但当 $a [i]$ 很小时，就几乎要遍历整个列表。

苦思冥想好几天之后点开Tutorial，发现给了一个非常巧妙的办法，就是利用 $\sqrt{n}$ 作为大小的分界线。对于 $a [i] \geq \sqrt{n}$ 的引索，搜索全部可能的 $k$ ，对于 $a [i] < \sqrt{n}$ 的引索，搜索小于 $\sqrt{n}$ 的 $k$ 。这样子：

若 $a [i] \geq \sqrt{n}, a [j] \geq \sqrt{n}$ ，有 $a [i] a [j] \geq n > n - 1$ ，不可能存在这样的对；
若 $a [i] \geq \sqrt{n}, a [j] < \sqrt{n}$ ，会被第一种方式搜到；
若 $a [i] < \sqrt{n}, a [j] < \sqrt{n}$ ，因此有 $k = a [j] < \sqrt{n}$ ，一定能被第二种方法搜到。这样子整个算法就能在 $O (n^{3 / 2})$ 的速度下完成计算。
这道题目的思路让我感觉是一种“Meet In Between"的思路。就是你有两种搜索方案，一共要完成 $n$ 的搜索任务，要么是给两者分别分配 $O (n)$ 与 $O (1)$ 的任务量，要么是给两者分配 $O (\sqrt{n})$ 的工作量。显然后面这种更优秀。这种方式在魔方求解最短步数的计算机解法里面也有利用，就是分别从初始状态与最终完成两个点进行bfs，看什么时候两者相遇。代码：

python

from math import sqrt, ceil
def solve():
	n = int(input())
	sqn = ceil(sqrt(n))
	a = list(map(int, input().split()))
	count = 0
	for i in range(n):
		current = a[i]
		if current >= sqn:
			for j in range(i % current, n, current):
				if a[i] * a[j] == abs(j - i):
					count += 1
		else:
			for j in range(i + current, min(i + sqn * current, n), current):
				if a[i] * a[j] == j - i:
					count += 1

	print(count)

t = int(input())
for _ in range(t):
	solve()

2196B: Another Problem about Beautiful Pairs ​

2196B: Another Problem about Beautiful Pairs