問題一覧 > 教育的問題

No.1746 Sqrt Integer Segments

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 43
作問者 : null / テスター : otera
お気に入りにしたユーザー ProblemId : 6811 / 自分の提出
問題文最終更新日: 2022-04-25 23:42:07
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

You are given a sequence $\{a_i\}$ of positive integers of length $n$.

Count the intervals $I=[l, r] (1 \le l \le r \le n)$ satisfying $\sqrt{\prod_{i \in I} a_i} \in \mathbb{Z}$.

Constraints

  • $1 \le n \le 2 \times 10^5$
  • $1 \le a_i \le 10^6$
  • All inputs are integers.

Input

$n$
$a_1\ a_2\ \dots\ a_n$

Output

Output the answer, followed by a newline.

Sample

Sample 1
Input
6
1 5 6 15 2 2
Output
4

Only $I=[1, 1], [5, 6], [2, 5], [1, 5]$ satisfy the condition.

Sample 2
Input
10
1 2 3 4 5 6 7 8 9 10
Output
3

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。