Это сложная версия задачи. Единственное отличие в том, что $$$1 \le x \le 5 \cdot 10^5$$$.
По пути домой после покупки своей любимой газировки «Zola Cero» Егор увидел, что в Саранске проходят выборы на пост «Лучшее число».
На избирательном участке с номером находятся $$$n$$$ человек. Каждый человек принес с собой число $$$a_i$$$. Когда $$$i$$$-й человек заходит в кабинку для голосования, он выбирает кандидата, который является делителем числа $$$a_i$$$. Обозначим выбранного кандидата через $$$p_i$$$.
После того как все проголосовали, получился массив голосов $$$[p_1, p_2, \ldots, p_n]$$$.
Егор очень любит число $$$x$$$ и считает голосование идеальным, если $$$x \cdot {lcm}(p_1, p_2, \ldots, p_n)$$$$$$^{\text{∗}}$$$ = $$$p_1 \cdot p_2 \cdot \ldots \cdot p_n$$$. Помогите ему найти количество различных$$$^{\text{†}}$$$ массивов $$$p$$$ по модулю $$$10^9 + 7$$$, которые являются идеальными.
$$$^{\text{∗}}$$$$$$lcm$$$ — наименьшее общее кратное.
$$$^{\text{†}}$$$Два массива голосов считаются различными, если существует индекс $$$i$$$, в котором два массива имеют отличные друг от друга элементы.
В первой строке записано одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.
Далее следуют $$$t$$$ наборов входных данных.
В первой строке каждого набора записаны два целых числа $$$n$$$ и $$$x$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq x \leq 5 \cdot 10^5$$$) — число голосующих в избирательном участке и любимое число Егора.
Во второй строке каждого набора записаны $$$n$$$ целых чисел: $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 5 \cdot 10^5$$$) — числа, которые принесли с собой голосующие.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите количество способов по модулю $$$10^9 + 7$$$ провести выборы так, чтобы итоговый массив голосов удовлетворял условию.
52 22 41 557 42 4 8 13 111 6 73 10001 2 33 34 8 10
2036000
| Codeforces Round 1103 (Div. 3) |
|---|
| Закончено |
