[SNOI2024] 平方数
题目背景
原题时间限制为 1.5 s。
由于 hack 数据难以通过,改为 10 s。
题目描述
你有一个正整数序列 $a_1, a_2, \ldots, a_n$。请问有多少个区间的乘积是完全平方数。也就是有多少对 $(l, r)$($1 \le l \le r \le n$),满足 $\prod_{i = l}^{r} a_i$ 是完全平方数。
输入输出格式
输入格式
第一行一个整数 $n$ 表示数字个数。
接下来一行,每行 $n$ 个数,表示 $a_1, a_2, \ldots, a_n$。
输出格式
输出一个整数,表示有多少对区间的乘积是完全平方数。
接下来按照字典序输出这些区间,也就是按照 $l$ 从小到大输出。
如果有多个 $l$ 相同的区间,按照 $r$ 从小到大输出。如果区间个数超过 ${10}^5$ 个,输出前 ${10}^5$ 个即可。
输入输出样例
输入样例 #1
10
1 2 3 4 6 8 9 12 16 18
输出样例 #1
12
1 1
1 5
2 5
3 6
3 7
4 4
4 8
4 9
5 8
5 9
7 7
9 9
输入样例 #2
3
999999999999999956000000000000000363 999999999999999844000000000000004059 999999999999999866000000000000001353
输出样例 #2
1
1 3
说明
**【样例 \#2 解释】**
在第二个样例中,这三个数为 ${10}^{18} - 11, {10}^{18} - 33, {10}^{18} - 123$ 两两相乘。
---
**【样例 \#3】**
见附件中 `square/square3.in` 与 `square/square3.ans`。
这个样例满足测试点 $4 \sim 6$ 的条件限制。
---
**【样例 \#4】**
见附件中 `square/square4.in` 与 `square/square4.ans`。
这个样例满足测试点 $11 \sim 14$ 的条件限制。
---
**【样例 \#5】**
见附件中 `square/square5.in` 与 `square/square5.ans`。
这个样例满足测试点 $18 \sim 20$ 的条件限制。
---
**【数据范围】**
对于所有的数据,保证 $1 \le n \le 3 \times {10}^5$,$1 \le a_i \le {10}^{36}$。
具体如下:
| 测试点编号 | $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}$ |