4484 - 区间乘积

讨论

统计

通过次数

提交次数

旧版界面

时间限制 : 1 秒

内存限制 : 128 MB

小杨有一个包含 $n$ 个正整数的序列 $A=[a_1,a_2,\ldots,a_n]$ 。

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

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

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

第二行包含 $n$ 个正整数 $a_i$ ，代表序列 $A$ 。

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

5
3 2 4 3 2

满足条件的 $\langle l,r\rangle$ 有 $\langle 1,5\rangle$ 和 $\langle 3,3\rangle$ 。

子任务编号	数据点占比	$n$	$a_i$
$1$	$20\%$	$\leq 10^5$	$1\leq a_i\leq 2$
$2$	$40\%$	$\leq 100$	$1\leq a_i\leq 30$
$3$	$40\%$	$\leq 10^5$	$1\leq a_i\leq 30$

GESP