기약분수

시간 제한3초메모리 제한2048 MB

요약

서로 다른 인덱스 네 개 (i, j, k, l)를 골라 (a_i * a_j) / (a_k * a_l)이 기약분수가 되는 경우의 수를 셉니다. 배열 길이는 최대 2000이고 원소는 최대 10^12입니다.

문제

길이가 $n$ 인 양의 정수 배열 $a$ 가 주어진다. 다음 분수가 기약분수가 되는, 서로 다른 인덱스 $(i, j, k, l)$ 의 네 쌍의 개수를 구하라.

$\frac{a_i \cdot a_j}{a_k \cdot a_l}$

첫째 줄에 배열의 길이 $n$ ( $4 \leq n \leq 2000$ )이 주어진다. 둘째 줄에는 배열의 원소 $a_i$ ( $1 \leq a_i \leq 10^{12}$ ) $n$ 개가 주어진다.

조건을 만족하는 인덱스 네 쌍의 개수를 정수 하나로 출력한다.