백준 시철이가 사랑한 수식을 브루트 포스로 검수한 썰

 어느덧 500번째 글입니다. 그냥 정보글은 시시하니, 대회 검수 썰을 풀어보도록 하겠습니다. SUAPC를 검수하면서 신경을 썼던 것 중 하나는, 대회에 출제된 20940번 문제였습니다. 대회에 출제된 문제 중에 난이도가 높은 그룹에 속할 것이라고 예상했고, 실제로 그렇게 되었습니다. 이 문제를 검수할 때 세웠던 원칙 중 하나는 브루트 포스로 검증을 해 볼만한 사이즈가 되면, 검증을 해 보자는 것이였습니다. 100만이면 모르겠지만, 50만이면 해 볼 만 했습니다. 잘 돌리면 1시간 정도에 해결을 할 수 있었기 때문입니다.

 

---

 이 문제의 초기 조건은 N은 [1, 50만], K는 10^9+7이였습니다. 브루트 포스로 돌릴 만 합니다. 그런데, 이걸 그냥 브루트 포스로 돌리기에는? N이 대충 50만. 50만의 제곱은 2500억이고, 1초에 1억개의 연산이 돈다고 했을 때, 뒤에 로그가 붙으면 상당히 오래 걸릴 수 있었습니다. 뒤에 로그는 gcd나 lcm을 N^2개의 쌍에 대해서 돌릴 때 붙습니다.

 

 로그가 붙어서 브루트 포스 솔루션을 돌리는 데 얼마나 걸렸을지는 생략하겠습니다. 로그를 떼는 게 목적입니다. 먼저, naive하게 검수를 하기는 할 건데, 효율적으로 하기 위해서는 관찰을 몇 가지 해야 합니다.

 

 

 먼저, gcd(i, 1) + ... + gcd(i, n)을 어떻게 구할지 생각해 봅시다. 그 전에, 최대 공약수가 무엇인지 생각해 봅시다. 공약수 중에 최댓값을 의미합니다. 그러면, i와 j의 공약수는 무엇을 의미할까요?

 

 k가 i의 약수이면서, j의 약수이면 됩니다. 쿼리의 특성을 보면, 어찌 되었던 i가 고정된 상황에서 j가 1부터 최대 50만까지 변하고 있는 상황입니다. 그러면 gcd(i, j)가 될 수 있는 값들은 i의 약수들일 겁니다. 이것이 핵심 관찰이 됩니다. 아무런 알고리즘도 쓰지 않고, 적당히 빠른 naive한 솔루션을 아래와 같은 알고리즘으로 설계할 수 있습니다.

 

 (2)번이 무슨 말인지 제가 봐도 잘 모르겠으니, i가 6인 경우를 예로 들어서 설명해 보겠습니다.

 

 

 처음에 gcd를 저장하는 배열은 모두 0으로 초기화 되어 있습니다. 6의 약수는 1, 2, 3, 6입니다.

 

 

 1의 배수들을 모두 1로 체크합니다. 그러면, 1의 배수들이 모두 체크될 겁니다.

 

 

 다음에 2의 배수들을 체크합니다. 2, 4, 6이 2로 업데이트 됩니다.

 

 

 그리고 3의 배수를 체크합니다. 3, 6이 3의 배수이니, 3과 6이 3으로 업데이트 됩니다.

 

 

 다음에 6의 배수만 업데이트 합니다. 6만 6으로 업뎃이 될 겁니다. 이 내용을 간단하게 코드로 구현하면 아래와 같습니다.

 

 

 7번째 줄을 보시면 1부터 x까지 도는데요. x가 i로 나누어 떨어지지 않으면 continue를 합니다. 그렇지 않으면, x가 i로 나누어 떨어진다는 것입니다. i의 배수를 k라 하면 gg[k]를 i로 채웁니다. 그게 다입니다. 여기서 하나 질문. 저렇게 약수를 for loop를 돌면서 구하면, 비효율적이지 않나요? 네. 그런데 어짜피 상수 차이이니 별 신경쓰지 않아도 됩니다.

 

 개선을 할 필요가 있다고 느껴지신다면, gg 배열의 값을 모두 1로 초기화 시켜 놓고, 1이 아닌 약수들만 가지고 계산해 주면 됩니다.

 

 호출하는 쪽에서는 이런 식으로 사용해 주시면 됩니다.

 

 

 실행 결과는 위와 같습니다.

 

---

 그런데, 저거 정말 로그를 뗄 수 있을까요? 네. 뗄 수 있습니다. 왜 그런지 알아 봅시다. 알고리즘을 잘 보면, k가 채워지는 조건을 알 수 있는데요. gg(i, j)의 공약수가 k일 때, k가 채워짐을 알 수 있어요. gcd(i, j)는 i와 j가 50만보다 작거나 같다면, 50만보다 작거나 같을 수 밖에 없어요. 이 점을 이용하시면, [1, 50만]의 범위에 있는 두 수 i, j의 최대 공약수는 [1, 50만] 사이에 있다는 것도 알 수 있어요.

 

 위 그림에서 행의 값과 열의 값은 각각 1, 2, 3, 4에 대응됩니다. gcd(행의 값, 열의 값) = 1이 되는 경우는 전체임을 알 수 있어요. 행이 n개이고, 열이 n개라면, gcd(행,열)이 1의 배수가 되는 가짓수는 n^2일 겁니다.

 

 

 그런데, gcd(행,열) = 2의 배수가 되는 경우는 어떨까요? 정말 놀랍도록 줄어듭니다. 아까의 16개에 비하면 1/4로 축소됩니다.

 

 

 gcd(행,열) = 3의 배수가 되는 경우는요? 대략 1/9라고 할 수 있어요. 위 그림에서는 하나밖에 없는데요. 4가 3의 배수가 아니기 때문입니다. 이것은 아래와 같이 다시 쓸 수 있습니다.

 

 

 이 때 주황색 부분은 링크에 따르면, (pi^2)/6 이라는 값의 상수입니다. 이걸 계산해 보면 약 1.5입니다. naive 솔루션의 복잡도를 N^2로 줄였다. N^2logN에서. 이것은 생각보다 크게 다가왔습니다. 17시간이 걸릴 일을 단 50분으로 줄여버렸습니다. 그래서, 브루트 포스 검증을 무사히 수행하게 되었습니다.