[codeforces] 1900D. Small GCD

문제 링크

크기가 $n$인 수열 $a$에 대하여 $\displaystyle\sum_{i=1}^{n}{\displaystyle\sum_{j=i+1}^{n}{\displaystyle\sum_{k=j+1}^{n}{f(a_{i}, a_{j}, a_{k})}}}$를 구하는 문제입니다. $f(x, y, z)$는 $x, y, z$중에서 가장 작은 두 값의 최대공약수입니다.

먼저 이 식을 변형 시켜봅시다. 어차피 세 수 중 가장 작은 두 값의 최대공약수를 구하므로 $a$를 오름차순으로 정렬한 수열을 $b$라고 하면

가 됩니다.

$S_{a} = \displaystyle\sum_{k=2}^{a}{\displaystyle\sum_{i=1}^{k}{\displaystyle\sum_{j=i+1}^{k}{\gcd(b_{i}, b_{j})}}} \;\, (2 \leq a \leq n-1)$라고 한다면 $S_{a}-S_{a-1} = \displaystyle\sum_{i=1}^{a}{\displaystyle\sum_{j=i+1}^{a}{\gcd(b_{i}, b_{j})}}$가 되고 $T_{a} = S_{a}-S_{a-1}$이라고 하면 $T_{a}-T_{a-1} = \displaystyle\sum_{i=1}^{a-1}{\gcd(b_{i}, b_{a})}$이 됩니다. 즉, 어떻게든 $\displaystyle\sum_{i=1}^{a-1}{\gcd(b_{i}, b_{a})}$를 계산하면 $T$의 다음 항을 구할 수 있고 또한, $S$의 다음항도 구할 수 있게 됩니다.

$\displaystyle\sum_{i=1}^{a-1}{\gcd(b_{i}, b_{a})}$는 아래와 같은 과정으로 계산합니다.
1. 이전부터 $b_{1}, ..., b_{a-1}$의 약수들을 카운트합니다.
2. $b_{a}$의 약수들을 큰 수 부터 작은 수 순으로 탐색합니다. 이 때, 아래 과정을 반복합니다.
$\quad$ 2-1. 1. 에서 $d$가 카운트된 횟수를 $cnt$라고 하면 $cnt \cdot d$를 더합니다. $\gcd(b_{i}, b_{a}) = d$인 $i$의 갯수가 $cnt$임을 의미하기 때문입니다. 그리고 1. 에서 카운트한 값들 중 $d$의 약수에 해당하는 카운트 값들을 $cnt$만큼 빼줍니다.

이렇게하면 다음 $T_{a}-T_{a-1}$를 구할 수 있고 위에서 설명했듯이 $S$의 다음항 또한 구할 수 있습니다.

지금까지 설명한 방법의 시간복잡도는 $O(n \cdot (\sqrt{\max(a)} + 2835))$입니다. 사실 이 시간복잡도만 놓고 봤을때는 2초가 되려나 싶었는데 390ms로 AC를 받았습니다. 코포는 AC를 받으면 테케를 공개해줘서 확인해봤는데 더 강한 데이터가 있는것 같긴하지만 그게 들어간다고 해도 제 답안이 TLE를 받을 것 같지는 않았습니다. 시간복잡도를 계산할 때 무언가 누락됐거나 딱히 무거운 연산이 없기도 해서 돌아가는 것 같기도 한데... 나중에 조금 더 살펴봐야겠습니다.