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

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解决方案(最大)代替。我所做的是:

拆分 b进入 bp和 bn其中第一个包含所有正数，第二个包含所有负数并创建了它们的映射。

然后:
2.1 我迭代 a获取 x的。
2.2 迭代 bn 中较短的一个和 bp .检查当前元素是否除x .如果是，请使用 map.find()看看是否z = -x/y是否存在。

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

Answer 1

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