题目背景

2024 年 6 月 GESP C++ 七级编程第 2 题

题目描述

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

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

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

输入格式

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

第二行包含 $n$ 个正整数 $a_1,a_2,...,a_n$ ，代表序列 $A$ 。

输出格式

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

样例

5
3 2 4 3 2

2

样例解释

满足条件的 $<l,r>$ 有 $<3,3>$ 和 $<1,5>$ 。

数据范围

对于全部数据，保证有 $1 \leq n \leq 10^5 , 1 \leq a_i \leq 30$ 。