P10063 [SNOI2024] Square Numbers

The original time limit was 1.5 s. Because it was hard to pass due to hack testdata, it was changed to 10 s.

You are given a sequence of positive integers $a_1, a_2, \ldots, a_n$. How many subarrays have a product that is a perfect square. In other words, how many pairs $(l, r)$ ($1 \le l \le r \le n$) satisfy that $\prod_{i = l}^{r} a_i$ is a perfect square.

The first line contains an integer $n$, the number of integers. The next line contains $n$ integers, $a_1, a_2, \ldots, a_n$.

Output one integer, the number of subarrays whose product is a perfect square. Then output these subarrays in lexicographical order, i.e., output by increasing $l$. If multiple subarrays have the same $l$, output them by increasing $r$. If the number of subarrays exceeds ${10}^5$, output only the first ${10}^5$.

**[Explanation for Sample \#2]** In the second sample, the three numbers are ${10}^{18} - 11, {10}^{18} - 33, {10}^{18} - 123$, and every pairwise product is computed. --- **[Sample \#3]** See the attachments `square/square3.in` and `square/square3.ans`. This sample satisfies the constraint limits of test points $4 \sim 6$. --- **[Sample \#4]** See the attachments `square/square4.in` and `square/square4.ans`. This sample satisfies the constraint limits of test points $11 \sim 14$. --- **[Sample \#5]** See the attachments `square/square5.in` and `square/square5.ans`. This sample satisfies the constraint limits of test points $18 \sim 20$. --- **[Constraints]** For all testdata, it is guaranteed that $1 \le n \le 3 \times {10}^5$, $1 \le a_i \le {10}^{36}$. Specifically: | Test Point ID | $n \le$ | $a_i \le$ | |:-:|:-:|:-:| | $1 \sim 3$ | $1000$ | ${10}^4$ | | $4 \sim 6$ | ${10}^5$ | ${10}^6$ | | $7 \sim 10$ | $100$ | ${10}^{36}$ | | $11 \sim 14$ | $1000$ | ${10}^{36}$ | | $15 \sim 17$ | ${10}^5$ | ${10}^{36}$ | | $18 \sim 20$ | $3 \times {10}^5$ | ${10}^{36}$ | Translated by ChatGPT 5