Есть массив, нужно уметь быстро (logn) отвечать на запросы "Сколько чисел в массиве делятся на x". Думал в сторону разряженных таблиц, но никаких результатов. Может кто-нибудь знает идею алгоритма или ссылку где это объясняется.
В массиве чисел 10^6 сами числа 10^9 Так что разложение на множители каждого не сработает.
Структуры, которые позволяют отсекать от множества ненужные элементы, а потом проверять оставшиеся, не подходят:
Предположим, что вам нужно найти чётные числа в массиве, который состоит ТОЛЬКО из чётных. Структура честно выдаст вам весь массив, а потом вам придётся проверять опять же весь.
То есть верхняя граница - O(n) проверок.
Я допускаю, что можно сделать среднюю оценку O(logN), например словари пар: (делитель->битовый массив) . Но считаю, что ответ всё же не в том, чтобы перебирать элементы, когда нужно найти КОЛИЧЕСТВО.
Тут нужно мозговать какую-то альтернативную систему хранения:
Например: число 20 с индексом i хранить как
2: i, i - отсортированный список делителей 2 с кратностью
5: i - аналогично про 5
Это позволит сократить поиск количества при разбиении x на множители.
Нужно будет оперировать списками-множествами.
Это завязано на длину списков, что сопоставимо с logN (даже меньше получится, так как N тут = корень (10^9), а не 10^6)
log(n) - похоже на дерево. Можно рассортировать их по двоичному дереву, каждый уровень которого представляет делимость на простое число: первый узел - делимость на 2, второй (в обеих ветвях) - на 3, третий (во всех ветвях) - на 5 и т. д. Понадобится O(n) доп. памяти, правда, зато скорость перебора - таки log(n).
log(n)?
Тогда вопрос только в том, как его ЗАРАНЕЕ отсортировать/какие доп структуры данных заранее создать. И, раз речь зашла о 10^6 и 10^9, то требования на доп структуры по памяти лучше тоже ограничить O(10^6). Так?
Поэтому разложение на множители заранее не отметайте. В каком-то виде оно может понадобиться, лишь бы требования соблюсти
ммм, может не так понимаю, но если числа целые O(n):
std::size_t count = 0;
for (std::size_t i = 0;i < arraysize(input); ++i) {
if (input[i] % x == 0) {
++count;
}
}
можно цикл распараллелить? [чепуха, читать ответы ниже]
а как долго у вас считается? если быстрее, вставляйте асм+MMX команды проца
⇢