[GESP202406 七级] 区间乘积
题目描述
小杨有一个包含 n 个正整数的序列 A=[a1,a2,…,an]。
小杨想知道有多少对 <l,r>(1≤l≤r≤n)满足 al×al+1×⋯×ar 为完全平方数。
一个正整数 x 为完全平方数当且仅当存在一个正整数 y 使得 x=y×y。
输入格式
第一行包含一个正整数 n,代表正整数个数。
第二行包含 n 个正整数 a1,a2,…,an,代表序列 A。
输出格式
输出一个整数,代表满足要求的 <l,r> 数量。
样例 #1
样例输入 #1
5
3 2 4 3 2
样例输出 #1
2
样例解释
满足条件的 <l,r> 有 <3,3> 和 <1,5>。
数据范围
| 子任务编号 |
数据点占比 |
n |
ai |
| 1 |
20% |
≤105 |
1≤ai≤2 |
| 2 |
40% |
≤100 |
1≤ai≤30 |
| 3 |
≤105 |
- 对于全部数据,保证有 1≤n≤105,1≤ai≤30。