Структуры, которые позволяют отсекать от множества ненужные элементы, а потом проверять оставшиеся, не подходят:
Предположим, что вам нужно найти чётные числа в массиве, который состоит ТОЛЬКО из чётных. Структура честно выдаст вам весь массив, а потом вам придётся проверять опять же весь.
То есть верхняя граница - O(n) проверок.
Я допускаю, что можно сделать среднюю оценку O(logN), например словари пар: (делитель->битовый массив) . Но считаю, что ответ всё же не в том, чтобы перебирать элементы, когда нужно найти КОЛИЧЕСТВО.
Тут нужно мозговать какую-то альтернативную систему хранения:
Например: число 20 с индексом i хранить как
2: i, i - отсортированный список делителей 2 с кратностью
5: i - аналогично про 5
Это позволит сократить поиск количества при разбиении x на множители.
Нужно будет оперировать списками-множествами.
Это завязано на длину списков, что сопоставимо с logN (даже меньше получится, так как N тут = корень (10^9), а не 10^6)