A66689 | $区间乘积$

来源2024年

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

3.2 编程题 2 试题名称：区间乘积 时间限制：1.0 s 内存限制：512.0 MB 3.2.1 题面描述 小杨有一个包含n个正整数的序列A=[a 1,a 2,\dots,a n]。 小杨想知道有多少对＜l,r＞(1\leql\leqr\leqn) 满足al\timesal+1\times\dots\timesa r 为完全平方数。 一个正整数x为完全平方数当且仅当存在一个正整数y使得x=y\timesy。 3.2.2 输入格式 第一行包含一个正整数n，代表正整数个数。 第二行包含n个正整数a 1,a 2,\dots,a n ，代表序列A。 3.2.3 输出格式 输出一个整数，代表满足要求的＜l,r＞数量。 3.2.4 样例1 3.2.5 样例解释 满足条件的＜l,r＞有＜3,3＞和＜1,5＞。 3.2.6 数据范围 对于全部数据，保证有1\leqn\leq10 5,1\leqa i \leq30。

C++ 编辑器

输入

输出