세 쌍 서로소

시간 제한2초메모리 제한512 MB

요약

값이 10^6 이하이고 길이가 10^5 이하인 수열에서 세 값의 최대공약수가 1인 인덱스 삼중항 i < j < k의 개수를 센다.

문제

크기가 $n$ 인 수열 $a_1, a_2, \dots, a_n$ 이 주어진다.

$1 \le i < j < k \le n$ 이면서 $\gcd(a_i, a_j, a_k) = 1$ 인 세 쌍 $(i, j, k)$ 의 개수를 구하는 프로그램을 작성하시오. 여기서 $\gcd$ 는 최대공약수를 뜻한다.

값이 같은 원소가 여러 번 나올 수 있고, 세 쌍은 값이 아니라 인덱스로 구분한다.

첫째 줄에 수열의 크기 $n$ ( $1 \le n \le 10^5$ )이 주어진다.

둘째 줄에 $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^6$ )이 공백으로 구분되어 주어진다.

첫째 줄에 조건을 만족하는 세 쌍 $(i, j, k)$ 의 개수를 출력한다.