The BOSS Can Count Pairs (Codeforces 1831D)
Tags: Math, binary search

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.

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)$$$. 

Sample Inputs:
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

Sample Outputs:
2
7
1

Solution (Python):
""""""

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        a = readIntArr()
        b = readIntArr()
        maxN = 0
        for aj in range(1, n + 1):
            for ai in range(1, aj + 1):
                if ai * aj > 2 * n:
                    break
                maxN = max(maxN, ai * (n + 1) + n)
        b_cnts = [0] * (maxN + 1)
        for i in range(n):
            X = a[i] * (n + 1) + b[i]
            if X <= maxN:
                b_cnts[X] += 1
        ans = 0
        same_ab = set()
        for j in range(n):
            (aj, bj) = (a[j], b[j])
            for ai in range(1, aj):
                bi = ai * aj - bj
                if bi <= 0:
                    continue
                if bi > n:
                    break
                chg = b_cnts[ai * (n + 1) + bi]
                ans += chg
            ai = aj
            if ai * aj <= 2 * n:
                bi = ai * aj - bj
                if 1 <= bi < bj:
                    ans += b_cnts[ai * (n + 1) + bi]
                elif bi == bj:
                    X = ai * (n + 1) + bi
                    same_ab.add(X)
        for X in same_ab:
            ans += b_cnts[X] * (b_cnts[X] - 1) // 2
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
for _ in range(int(input())):
    n = int(input())
    ta = list(map(int, input().split()))
    tb = list(map(int, input().split()))
    a = [(x, y) for (x, y) in zip(ta, tb)]
    a.sort()
    cnt = [0] * (2 * n + 1)
    pr = 0
    ans = 0
    for i in range(n):
        if pr != a[i][0]:
            pr = a[i][0]
            if pr * pr > 2 * n:
                break
            cnt = [0] * (2 * n + 1)
            for j in range(i + 1, n):
                t = a[i][0] * a[j][0] - a[j][1]
                if t >= 0 and t <= 2 * n:
                    cnt[t] += 1
        ans += cnt[a[i][1]]
        if i + 1 < n:
            t = a[i][0] * a[i + 1][0] - a[i + 1][1]
            if t >= 0 and t <= 2 * n:
                cnt[t] -= 1
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    a = tuple(map(int, input().split()))
    b = tuple(map(int, input().split()))
    x = sorted(((a[i], b[i]) for i in range(n)))
    limit = 2 * n + 1
    ans = prev = 0
    for i in range(n):
        if x[i][0] != prev:
            prev = x[i][0]
            if prev * prev >= limit:
                break
            count = [0] * limit
            for j in range(i + 1, n):
                temp = x[i][0] * x[j][0]
                if temp - limit >= 0:
                    break
                temp = temp - x[j][1]
                if temp in range(0, limit):
                    count[temp] += 1
        ans += count[x[i][1]]
        if i + 1 < n:
            temp = x[i][0] * x[i + 1][0] - x[i + 1][1]
            if temp in range(0, limit):
                count[temp] -= 1
    print(ans)