A6741. 「SNOI2024」平方数
编程题
NOI/NOI+/CTSC
知识点
题目描述
你有一个正整数序列 $a_1, a_2, \dots, a_n$。请问有多少个区间的乘积是完全平方数。也就是有多少对 $(l, r) (1\leq l\leq r \leq n)$，满足 $\prod_{i=l}^r a_i$ 是完全平方数。
输入格式
第一行一个整数 $n$ 表示数字个数。
接下来一行，每行 $n$ 个数，表示 $a_1, a_2, \dots, a_n$。
接下来一行，每行 $n$ 个数，表示 $a_1, a_2, \dots, a_n$。
输出格式
输出一个整数，表示有多少对区间的乘积是完全平方数。
接下来按照字典序输出这些区间，也就是按照 $l$ 从小到大输出，如果有多个 $l$ 相同的区间，按照 $r$ 从小到大输出。如果区间个数超过 $10^5$ 个，输出前 $10^5$ 个即可。
接下来按照字典序输出这些区间，也就是按照 $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
说明/提示
对于所有的数据，保证 $1\leq n \leq 3\times 10^5$, $1 \leq a_i\leq 10^{36}$。
具体如下：
| 测试点编号 | $n\leq$ | $a_i\leq$ |
|:----------:|:--------------:|:---------:|
| $1\sim3$ | $1000$ | $10^4$ |
| $4\sim6$ | $10^5$ | $10^6$ |
| $7\sim10$ | $100$ | $10^{36}$ |
| $11\sim14$ | $1000$ | $10^{36}$ |
| $15\sim17$ | $10^5$ | $10^{36}$ |
| $18\sim20$ | $3\times 10^5$ | $10^{36}$ |
具体如下：
| 测试点编号 | $n\leq$ | $a_i\leq$ |
|:----------:|:--------------:|:---------:|
| $1\sim3$ | $1000$ | $10^4$ |
| $4\sim6$ | $10^5$ | $10^6$ |
| $7\sim10$ | $100$ | $10^{36}$ |
| $11\sim14$ | $1000$ | $10^{36}$ |
| $15\sim17$ | $10^5$ | $10^{36}$ |
| $18\sim20$ | $3\times 10^5$ | $10^{36}$ |