POJ 3904 Sky Code

http://poj.org/problem?id=3904

 

$$\sum^{n-3}_{i=1}\sum^{n-2}_{j=i+1}\sum^{n-1}_{k=j+1}\sum^{n}_{l=k+1}[\gcd(a_i,a_j,a_k,a_l)=1]=\sum^{n-3}_{i=1}\sum^{n-2}_{j=i+1}\sum^{n-1}_{k=j+1}\sum^{n}_{l=k+1}\sum^{10000}_{d=1}[d|a_i][d|a_j][d|a_k][d|a_l]\mu(d)$$

$$=\sum^{10000}_{d=1}\mu(d)\sum^{n-3}_{i=1}[d|a_i]\sum^{n-2}_{j=i+1}[d|a_j]\sum^{n-1}_{k=j+1}[d|a_k]\sum^{n}_{l=k+1}[d|a_l]$$

 

수 범위가 작으니 각 \(d\)마다 확인할 배수가 \(\lfloor\frac{10000}{d}\rfloor\)개 밖에 없어서 배수들의 개수를 센 뒤 그 중 \(4\)개를 고르는 경우의 수를 계산해 \(O(n\log{n})\)만에 답을 구할 수 있다.