{"problem":{"name":"[SNOI2024] 平方数","description":{"content":"你有一个正整数序列 $a_1, a_2, \\ldots, a_n$。请问有多少个区间的乘积是完全平方数。也就是有多少对 $(l, r)$（$1 \\le l \\le r \\le n$），满足 $\\prod_{i = l}^{r} a_i$ 是完全平方数。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":10000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10063"},"statements":[{"statement_type":"Markdown","content":"你有一个正整数序列 $a_1, a_2, \\ldots, a_n$。请问有多少个区间的乘积是完全平方数。也就是有多少对 $(l, r)$（$1 \\le l \\le r \\le n$），满足 $\\prod_{i = l}^{r} a_i$ 是完全平方数。\n\n## Input\n\n第一行一个整数 $n$ 表示数字个数。  \n接下来一行，每行 $n$ 个数，表示 $a_1, a_2, \\ldots, a_n$。\n\n## Output\n\n输出一个整数，表示有多少对区间的乘积是完全平方数。  \n接下来按照字典序输出这些区间，也就是按照 $l$ 从小到大输出。  \n如果有多个 $l$ 相同的区间，按照 $r$ 从小到大输出。如果区间个数超过 ${10}^5$ 个，输出前 ${10}^5$ 个即可。\n\n[samples]\n\n## Background\n\n原题时间限制为 1.5 s。\n\n由于 hack 数据难以通过，改为 10 s。\n\n## Note\n\n**【样例 \\#2 解释】**\n\n在第二个样例中，这三个数为 ${10}^{18} - 11, {10}^{18} - 33, {10}^{18} - 123$ 两两相乘。\n\n---\n\n**【样例 \\#3】**\n\n见附件中 `square/square3.in` 与 `square/square3.ans`。\n\n这个样例满足测试点 $4 \\sim 6$ 的条件限制。\n\n---\n\n**【样例 \\#4】**\n\n见附件中 `square/square4.in` 与 `square/square4.ans`。\n\n这个样例满足测试点 $11 \\sim 14$ 的条件限制。\n\n---\n\n**【样例 \\#5】**\n\n见附件中 `square/square5.in` 与 `square/square5.ans`。\n\n这个样例满足测试点 $18 \\sim 20$ 的条件限制。\n\n---\n\n**【数据范围】**\n\n对于所有的数据，保证 $1 \\le n \\le 3 \\times {10}^5$，$1 \\le a_i \\le {10}^{36}$。\n\n具体如下：\n\n| 测试点编号 | $n \\le$ | $a_i \\le$ |\n|:-:|:-:|:-:|\n| $1 \\sim 3$ | $1000$ | ${10}^4$ |\n| $4 \\sim 6$ | ${10}^5$ | ${10}^6$ |\n| $7 \\sim 10$ | $100$ | ${10}^{36}$ |\n| $11 \\sim 14$ | $1000$ | ${10}^{36}$ |\n| $15 \\sim 17$ | ${10}^5$ | ${10}^{36}$ |\n| $18 \\sim 20$ | $3 \\times {10}^5$ | ${10}^{36}$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10063","tags":["各省省选","2024","O2优化","陕西"],"sample_group":[["10\n1 2 3 4 6 8 9 12 16 18\n","12\n1 1\n1 5\n2 5\n3 6\n3 7\n4 4\n4 8\n4 9\n5 8\n5 9\n7 7\n9 9\n"],["3\n999999999999999956000000000000000363 999999999999999844000000000000004059 999999999999999866000000000000001353\n","1\n1 3\n"]],"created_at":"2026-03-03 11:09:25"}}