P10724 [GESP202406 Level 7] Interval Product

Related multiple-choice and true/false questions: .

Xiao Yang has a sequence $A=[a_1,a_2,\ldots,a_n]$ containing $n$ positive integers. Xiao Yang wants to know how many pairs $\langle l,r\rangle(1\leq l\leq r\leq n)$ satisfy that $a_l\times a_{l+1}\times\ldots\times a_r$ is a perfect square. A positive integer $x$ is a perfect square if and only if there exists a positive integer $y$ such that $x=y\times y$.

The first line contains a positive integer $n$, representing the number of positive integers. The second line contains $n$ positive integers $a_i$, representing the sequence $A$.

Output an integer, representing the number of $\langle l,r\rangle$ pairs that meet the requirement.

### Sample Explanation The $\langle l,r\rangle$ pairs that satisfy the condition are $\langle 1,5\rangle$ and $\langle 3,3\rangle$. ### Constraints | Subtask ID | Percentage | $n$ | $a_i$ | | :-: | :-: | :-: | :-: | | $1$ | $20\%$ | $\leq 10^5$ | $1\leq a_i\leq 2$ | | $2$ | $40\%$ | $\leq 100$ | $1\leq a_i\leq 30$ | | $3$ | $40\%$ | $\leq 10^5$ | $1\leq a_i\leq 30$ | Translated by ChatGPT 5