找到与给定数字相乘的数字的有效方法

Question

我得到了2列表，a并且b. 它们都只包含整数。min(a) > 0，max(a)可高达1e10并且max(abs(b))可高达1e5。我需要找到元组的数量(x, y, z)，其中的x位置a和y, z位置是b这样的x = -yz。a和 中的元素数b最多可达1e5。

我的尝试：

我能够想出一个天真的n^2算法。但是，由于大小可以达到 1e5，因此我需要提出一个nlogn解决方案 (max)。我所做的是：

1. 拆分b成bp和bn，其中第一个包含了所有的正数和第二个包含所有的负数，并创建自己的地图。

2. 然后：

   2.1 我迭代a得到x的。

   2.2遍历的较短一个bn和bp。检查当前元素是否除x。如果是，则用于map.find()查看是否z = -x/y存在。

有什么有效的方法可以做到这一点？

Answer 1

这是一个未经测试的想法。从 的元素创建一个字典树b，其中“字符”是有序的素数。对于 中的每个元素a，遍历 trie 中的所有有效路径（DFS 或 BFS，其中测试能够进一步除以当前节点），并且对于到达的每个叶子，检查剩余元素是否（在每个节点处划分后）存在于b. （我们可能需要通过存储每个“单词”的计数并使用简单的组合来处理重复项。）