题目大意
给出 n n n 个数 a i a_i ai，求有多少对 ⟨ l , r ⟩ \lang l,r \rang ⟨l,r⟩，满足 1 ≤ l ≤ r ≤ n 1 \le l \le r \le n 1≤l≤r≤n 且 a l × a l + 1 × ⋯ × a r − 1 × a r a_l \times a_{l+1} \times \dots \times a_{r-1} \times a_r al×al+1×⋯×ar−1×ar 为完全平方数。
一个正整数 x x x 为完全平方数，当且仅当存在一个正整数 y y y，使得 x = y 2 x = y^2 x=y2。
思路讲解
阶段一：前缀积
首先，我们将问题进行一个类似前缀和的转化。
设 p i p_i pi 为 ∏ j = 1 i a j \prod_{j=1}^{i} a_j ∏j=1iaj，即序列 A A A 前 i i i 个数的乘积，则题目可转换为存在多少对 ⟨ l , r ⟩ \lang l,r \rang ⟨l,r⟩，满足 p r p l − 1 ( p 0 = 1 ) \frac{p_r}{p_{l-1}}(p_0 = 1) pl−1pr
最低0.47元/天 解锁文章
扫一扫
514
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
