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

我得到了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)。我所做的是:

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

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

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

最佳答案

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

关于c++ - 查找与给定数字相乘的数字的有效方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/60125740/