g7-02622. GESP-7级-2024-06-区间乘积

题目描述

小杨有一个包含 $n$ 个正整数的序列 $A = [a_{1}, a_{2}, \dots, a_{n}]$ 。

小杨想知道有多少对 ${l, r} (1 \leq l \leq r \leq n)$ 满足 $a_{l} \times a_{l + 1} \times \dots \times a_{r}$ 为完全平方数。

一个正整数 $x$ 为完全平方数当且仅当存在一个正整数 $y$ 使得 $x = y \times y$ 。

第一行包含一个正整数 $n$ ，代表正整数个数。

第二行包含 $n$ 个正整数 $a_{i}$ ，代表序列 $A$ 。

输出一个整数，代表满足要求的 $⟨ l, r ⟩$ 数量。

输入

5
3 2 4 3 2

输出

满足条件的 ${l, r}$ 有 ${1, 5}$ 和 ${3, 3}$ 。

子任务编号	数据点占比	$n$	$a_{i}$
$1$	$20%$	$\leq 1 0^{5}$	$1 \leq a_{i} \leq 2$
$2$	$40%$	$\leq 100$	$1 \leq a_{i} \leq 30$
$3$	$40%$	$\leq 1 0^{5}$	$1 \leq a_{i} \leq 30$

来源：洛谷 P10724（CCF GESP 七级上机题）