D. The BOSS Can Count Pairs

You are given two arrays $a$ and $b$, both of length $n$.

Your task is to count the number of pairs of integers $(i,j)$ such that $1 \leq i < j \leq n$ and $a_i \cdot a_j = b_i+b_j$.

Input

Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the arrays.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le n$) — the elements of array $a$.

The third line of each test case contains $n$ integers $b_1,b_2,\ldots,b_n$ ($1 \le b_i \le n$) — the elements of array $b$.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output the number of good pairs.

Example

input

3
3
2 3 2
3 3 1
8
4 2 8 2 1 2 7 5
3 5 8 8 1 1 6 5
8
4 4 8 8 8 8 8 8
8 8 8 8 8 8 8 8

output

2
7
1

Note

In the first sample, there are $2$ good pairs:

• $(1,2)$,
• $(1,3)$.

In the second sample, there are $7$ good pairs:

• $(1,2)$,
• $(1,5)$,
• $(2,8)$,
• $(3,4)$,
• $(4,7)$,
• $(5,6)$,
• $(5,7)$.

解题思路

　　枚举优化题，先给出我一开始的思路。因为$1 \leq b_i \leq n$，因此有$a_i \times a_j = b_i + b_j \leq 2n$，所以当时就想到从$1$开始枚举到$2n$作为$a_i \times a_j$的结果，记作$x$。然后对$x$进行约数分解，那么就会得到$a_i$和$a_j$。接着枚举所有值为$a_i$的下标$u$，然后再从所有值为$a_j$的下标中二分出来大于$u$的最小下标$v$，然后在所有值为$a_j$的且不超过$v$的下标中统计数值恰好为$a_i \times a_j - b_u$的个数，这就是答案数对的数目。

　　很明显这种做法肯定会超时，需要优化的地方为统计数值恰好为$a_i \times a_j - b_u$的个数，但很复杂我没写出来，即便写出来时间复杂度也是$O(n \sqrt{n} \log{n})$，还是会超时。不过如果提前预处理每个数约数分解的结果那么$\sqrt{n}$计算量的分解部分就会大大降低，有可能会过。

　　下面给出正解。

　　首先我们知道了$a_i \times a_j \leq 2n$，因此必然有$\min \{ a_i, a_j \} \leq \sqrt{2n}$。由于题目中要求统计的数对$(i,j)$要满足$i<j$，但如果按照$a_i \leq a_j$的规则来统计数对得到的答案是一样的。其中如果有$a_i < a_j$且$i>j$，那么我们只需交换$i$和$j$，可以发现得到的数对是一样的，因此接下来我们只统计$a_i \leq a_j$的数对。

　　由于已经假设$a_i \leq a_j$，因此有$a_i \leq \sqrt{2n}$，所以我们从$1$到$\sqrt{2n}$来枚举$a_i$的值（$a$中可能不存在这个值），然后再枚举一遍序列$a$找到大于等于$a_i$的$a_j$，此时就可以确定$b_i$的取值，即$a_i \times a_j - b_j$。那么满足条件的数对数量就是序列$a$和$b$中满足$(a_k, b_k) = (a_i, b_i)$的数量（前提是算出的$b_i$要满足$1 \leq b_i \leq n$）。

　　为此我们可以先对数对$(a_k, b_k)$以$a_k$为关键字进行排序，在枚举确定每一个$a_i$后开一个数组$\text{cnt}$来统计数对$(a_i, b_i)$的数量，由于$a_i$已经是一个确定值，因此$\text{cnt}[x]$则表示所有$a_k = a_i$并且$b_k = x$的数对数量。由于序列$a$已经升序排序，因此在枚举$a_j$时边枚举边统计即可，当然只统计$a_j = a_i$对应的$b_j$。因此对于某个$a_j$，满足等式的数对数量就是$\text{cnt}[a_i \times a_j - b_j]$（下标严格小于$j$的数对数量）。这样就可以避免重复枚举，且没有枚举到两个相同下标的情况。

　　AC代码如下，时间复杂度为$O(n \sqrt{n})$：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 
 6 const int N = 2e5 + 10;
 7 
 8 int a[N], b[N], p[N];
 9 int cnt[N];
10 
11 void solve() {
12     int n;
13     scanf("%d", &n);
14     for (int i = 0; i < n; i++) {
15         scanf("%d", a + i);
16     }
17     for (int i = 0; i < n; i++) {
18         scanf("%d", b + i);
19     }
20     for (int i = 0; i < n; i++) {
21         p[i] = i;
22     }
23     sort(p, p + n, [&](int i, int j) {
24         return a[i] < a[j];
25     });
26     LL ret = 0;
27     for (int i = 1; i * i <= n << 1; i++) {
28         memset(cnt, 0, n + 10 << 2);
29         for (int j = 0; j < n; j++) {
30             int t = i * a[p[j]] - b[p[j]];
31             if (t >= 1 && t <= n) ret += cnt[t];
32             if (i == a[p[j]]) cnt[b[p[j]]]++;
33         }
34     }
35     printf("%lld\n", ret);
36 }
37 
38 int main() {
39     int t;
40     scanf("%d", &t);
41     while (t--) {
42         solve();
43     }
44     
45     return 0;
46 }

参考资料

　　Codeforces Round 875 (Div. 2) D (思维 + 枚举)：https://zhuanlan.zhihu.com/p/633099878