题目背景

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

题目描述

给定一个长度为 $n$ 的正整数序列 $A=[a_1,a_2,\ldots,a_n]$。请统计有多少个区间 $[l,r]$（$1 \le l\le r \le n$），使得区间乘积 $a_l a_{l+1}\cdots a_r$ 是完全平方数。

输入格式

第一行输入正整数 $n$。 第二行输入 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一行一个整数，表示满足条件的区间数量。

5
3 2 4 3 2

2

数据范围与提示

• $1 \le n\le 10^5$。
• $1 \le a_i \le 30$；部分数据满足 $a_i \le 2$ 或 $n \le 100$。
• 样例中满足条件的区间为 $[3,3]$ 和 $[1,5]$。

来源

GESP 2024 年 06 月 C++ 七级 T2