Эффективный способ найти числа, которые умножаются на заданные числа

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

Вот непроверенная идея. Создайте tr ie из элементов b, где "символы" - это упорядоченные простые числа. Для каждого элемента в a пройдитесь по всем действительным путям в tr ie (DFS или BFS, где тест может делиться дальше по текущему узлу), и для каждого достигнутого листа проверьте, если оставшийся элемент ( после деления на каждый узел) существует в b. (Возможно, нам придется обрабатывать дубликаты, сохраняя счет каждого «слова» и используя простую комбинаторику.)