Sky Code

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

요약

최대 10000개의 별 ID가 주어질 때, 네 개를 고른 부분집합 중 최대공약수가 1인 경우의 수를 뫼비우스 함수를 이용해 구합니다.

난이도: 보통10점 중 6점
유형: 정수론, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

우주여행을 좋아하는 스탄쿠는 실력이 부족한 소프트웨어 개발자라서 자신의 우주선을 살 수 없다. 그래서 그는 페트루의 우주선을 훔치려고 준비하고 있다. 문제가 하나 있는데, 페트루가 우주선을 은하수(밀키웨이) 은하에 있는 별들의 ID 번호를 이용한 정교한 암호 시스템으로 잠가 두었다는 것이다.

이 시스템을 뚫으려면 스탄쿠는 네 별의 ID 번호의 유일한 공약수가 1인, 즉 네 수의 최대공약수가 1인 네 별의 부분집합을 모두 확인해야 한다. 다행히 스탄쿠는 관심 있는 별의 수를 $N$ 개로 줄였지만, 그런 네 별의 부분집합의 수는 여전히 매우 많을 수 있다.

그 부분집합의 개수를 세어 시스템을 뚫을 가능성이 있는지 판단하도록 그를 도와라.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 관심 있는 별의 수 $N$ 이 주어진다( $1 \le N \le 10000$ ). 둘째 줄에는 관심 있는 별들의 ID 번호가 공백으로 구분되어 주어진다. 각 ID는 10000보다 크지 않은 양의 정수이다. 입력은 파일의 끝에서 종료된다.

출력

각 테스트 케이스에 대해, ID 번호의 최대공약수가 1인 네 별의 부분집합의 개수를 한 줄에 출력한다.

예제3

예제 1

입력

4
2 3 4 5
4
2 4 6 8
7
2 3 4 5 7 6 8

예상 출력

1
0
34

예제 2
입력
```
3
6 10 15
```
예상 출력
```
0
```
예제 3
입력
```
5
2 3 5 7 11
```
예상 출력
```
5
```