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≤i<j≤n and ai⋅aj=bi+bj .
时间: 2024-02-04 14:01:40 浏览: 29
To solve this problem, we can first preprocess the array b to create a hash table that maps each value in b to its frequency. Then, for each pair of indices (i,j) such that i<j, we can check if ai⋅aj is equal to bi+bj by computing ai/bj and aj/bi and checking if they are equal. If they are equal, we can check if the values ai/bj and aj/bi are present in the hash table. If both values are present, we can increment our count by the product of their frequencies in the hash table.
The time complexity of this algorithm is O(n^2) due to the nested loops, but the constant factor is small due to the hash table lookups. Here is the Python code for the algorithm:
```
from collections import defaultdict
def count_pairs(a, b):
n = len(a)
freq = defaultdict(int)
for x in b:
freq[x] += 1
count = 0
for i in range(n):
for j in range(i+1, n):
if a[i]*a[j] == b[i]+b[j]:
if b[i] != 0 and b[j] % b[i] == 0 and a[j] == (b[j] // b[i]) * a[i]:
x = b[i]
y = b[j] // b[i]
if x in freq and y in freq:
count += freq[x] * freq[y]
if b[j] != 0 and b[i] % b[j] == 0 and a[i] == (b[i] // b[j]) * a[j]:
x = b[j]
y = b[i] // b[j]
if x in freq and y in freq:
count += freq[x] * freq[y]
return count
```
Note that we need to check both possible orderings of ai and aj in case one of them is zero or the corresponding value in b is not present in the hash table.