Codeforces Round 954 (Div. 3) |
---|
Закончено |
Это сложная версия задачи. Единственное различие состоит в том, что в этой версии $$$n \leq 5 \cdot 10^5$$$ и сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.
Вам дана перестановка $$$p$$$ длины $$$n$$$. Посчитайте количество пар индексов $$$1 \leq i < j \leq n$$$, таких что $$$p_i \cdot p_j$$$ делится без остатка на $$$i \cdot j$$$.
Перестановка — это последовательность из $$$n$$$ целых чисел, в которой каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно по одному разу. Например, $$$[1]$$$, $$$[3,5,2,1,4]$$$, $$$[1,3,2]$$$ — перестановки, а $$$[2,3,2]$$$, $$$[4,3,1]$$$, $$$[0]$$$ — нет.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует их описание.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) — длина перестановки $$$p$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — перестановку $$$p$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.
Для каждого набора входных данных выведите количество пар индексов $$$1 \leq i < j \leq n$$$, таких что $$$p_i \cdot p_j$$$ делится без остатка на $$$i \cdot j$$$.
61121 232 3 152 4 1 3 5128 9 7 12 1 10 6 3 2 4 11 5151 2 4 6 8 10 12 14 3 9 15 5 7 11 13
0 1 1 3 9 3
В первом наборе входных данных нет ни одной пары индексов, так как размер перестановки равен $$$1$$$.
Во втором наборе входных данных есть одна пара индексов $$$(1, 2)$$$ и она подходит.
В третьем наборе входных данных подходит пара индексов $$$(1, 2)$$$.
В четвертом наборе входных данных подходят пары индексов $$$(1, 2)$$$, $$$(1, 5)$$$ и $$$(2, 5)$$$.
Название |
---|