#G1057. [GESP202406 七级] 区间乘积

[GESP202406 七级] 区间乘积

[GESP202406 七级] 区间乘积

题目描述

小杨有一个包含 nn 个正整数的序列 A=[a1,a2,…,an]A = [a_1, a_2, \dots, a_n]。

小杨想知道有多少对 <l,r><l, r>(1≤l≤r≤n1 ≤ l ≤ r ≤ n)满足 al×al+1×⋯×ara_l \times a_{l+1} \times \dots \times a_r 为完全平方数。

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

输入格式

第一行包含一个正整数 nn,代表正整数个数。

第二行包含 nn 个正整数 a1,a2,…,ana_1, a_2, \dots, a_n,代表序列 AA。

输出格式

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

样例 #1

样例输入 #1

5
3 2 4 3 2

样例输出 #1

2

样例解释

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

数据范围

子任务编号 数据点占比 nn aia_i
1 20% ≤105≤ 10^5 1≤ai≤21 ≤ a_i ≤ 2
2 40% ≤100≤ 100 1≤ai≤301 ≤ a_i ≤ 30
3 ≤105≤ 10^5
  • 对于全部数据,保证有 1≤n≤1051 ≤ n ≤ 10^5,1≤ai≤301 ≤ a_i ≤ 30。