Geometric Progression

시간 제한1초메모리 제한1024 MB

요약

최대 백만 개의 정수가 엄격히 증가하는 수열로 주어질 때 i < j < k이고 a_i * a_k = a_j^2인 세 쌍의 개수를 센다. 값이 서로 다르다는 조건이 핵심이며, 중간항의 제곱 조건은 소인수분해로 다시 쓸 수 있다.

문제

bobo loves geometric progressions! So he wants to know the number of geometric progressions of length $3$ in a sequence $a\_1, a\_2, \dots, a\_n$ .

That is to say, count the number of $(i, j, k)$ where $i < j < k$ and $a\_{i} \cdot a\_{k} = a\_j^2$ .

The first line contains an integer $n$ ( $1 \leq n \leq 1000000$ ).

The second line contains $n$ integers $a\_1, a\_2, \dots, a\_n$ ( $1 \leq a\_1 < a\_2 < \dots < a\_n \leq 1000000$ ).

A single integer denotes the number of geometric progressions.