[SNOI2024] 平方数

Luogu

IDLGP10063

Time10000ms

Memory1024MB

DifficultyP7

各省省选2024O2优化陕西

你有一个正整数序列 $a_1, a_2, \ldots, a_n$。请问有多少个区间的乘积是完全平方数。也就是有多少对 $(l, r)$（$1 \le l \le r \le n$），满足 $\prod_{i = l}^{r} a_i$ 是完全平方数。 ## Input 第一行一个整数 $n$ 表示数字个数。接下来一行，每行 $n$ 个数，表示 $a_1, a_2, \ldots, a_n$。 ## Output 输出一个整数，表示有多少对区间的乘积是完全平方数。接下来按照字典序输出这些区间，也就是按照 $l$ 从小到大输出。如果有多个 $l$ 相同的区间，按照 $r$ 从小到大输出。如果区间个数超过 ${10}^5$ 个，输出前 ${10}^5$ 个即可。 [samples] ## Background 原题时间限制为 1.5 s。由于 hack 数据难以通过，改为 10 s。 ## Note **【样例 \#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}$ |

Samples

Input #1

10
1 2 3 4 6 8 9 12 16 18

Output #1

Input #2

3
999999999999999956000000000000000363 999999999999999844000000000000004059 999999999999999866000000000000001353

Output #2

1
1 3

API Response (JSON)

{
  "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_...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments