[BOJ 3752] 최대공약수 행렬식

집합 $s$는 크기가 $n$이고 어떤 자연수 $m$의 약수를 모두 포함하고 있다. 그 집합의 원소들에 대해 다음 행렬을 만들었을 때 행렬식을 구하는 문제이다.

\[D_{n}=\begin{vmatrix} \gcd(x_{1},x_{1}) & \gcd(x_{1},x_{2}) & ... & \gcd(x_{1},x_{n})\\ \gcd(x_{2},x_{1}) & \gcd(x_{2},x_{2}) & ... & \gcd(x_{2},x_{n})\\ ... & ... & ... & ...\\ \gcd(x_{n},x_{1}) & \gcd(x_{n},x_{2}) & ... & \gcd(x_{n},x_{n})\\ \end{vmatrix}\]

행렬식을 계산할 때 가장 단순하게 생각할 수 있는 것은 대각 행렬의 꼴을 만든 뒤에 대각 성분의 곱을 구하는 것이다. 그럼 주어진 행렬을 row echlon form으로 만들며 규칙을 알아보자.

다음과 같은 집합을 생각해보자. $s={1,2,3,6,9,18}$ 그럼 행렬을 다음과 같이 만들 수 있다.

\[A=\begin{vmatrix} 1&1&1&1&1&1 \\ 1&2&1&2&1&2 \\ 1&1&3&3&3&3 \\ 1&2&3&6&3&6 \\  1&1&3&3&9&9 \\ 1&2&3&6&9&18 \\ \end{vmatrix}\]

맨 앞의 1을 없애기 위해 1번째 열을 나머지 열에 빼주자. (행렬식은 방금과 같은 row operation에 영향을 받지 않는다.)

\[=\begin{vmatrix} 1&1&1&1&1&1 \\ 0&1&0&1&0&1 \\ 0&0&2&2&2&2 \\ 0&1&2&5&2&5 \\  0&0&2&2&8&8 \\ 0&1&2&5&8&17 \\ \end{vmatrix}\]

$\gcd(ak,a)$가 $ak$이하의 $k$의 배수의 개수라 생각해보자. 대각 성분의 앞의 부분이 전부 0인 열의 대각 성분만 고려하면 $A_{2,2}=2$가 1로 바뀌었고 $A_{3,3}=3$이 2로 바뀌었다. 그 의미는 $2$에서 2의 배수를 제외했다는 것, $3$에서 3의 배수를 제외했다는 것으로 해석된다. 그럼 2번째, 3번째 열을 이용해 나머지 열을 대각화 해주자.

\[=\begin{vmatrix} 1&1&1&1&1&1 \\ 0&1&0&1&0&1 \\ 0&0&2&2&2&2 \\ 0&0&2&4&2&4 \\  0&0&2&2&8&8 \\ 0&0&2&4&8&16 \\ \end{vmatrix}\]

\[=\begin{vmatrix} 1&1&1&1&1&1 \\ 0&1&0&1&0&1 \\ 0&0&2&2&2&2 \\ 0&0&0&2&0&2 \\  0&0&0&0&6&6 \\ 0&0&0&2&6&14 \\ \end{vmatrix}\]

$A_{4,4}$를 보자. 원래의 값은 6이었다. 가장 처음 진행한 연산부터 차근차근 생각해보자. 맨 처음에는 6까지의 6의 배수의 개수가 빠졌다(-1). 그 다음은 6까지 6이 아닌 2의 배수의 개수가 빠졌다(-2). 그 다음은 6까지 6이 아닌 3의 배수의 개수가 빠졌다(-1). 그래서 2가 된 것이다.  6이 아닌 2의 배수가 된 이유는 6까지의 2의 배수 중에서 1번째 열의 연산으로 인해 6의 배수가 빠졌기 때문이다. 이러한 전개를 거치면 현재 $A_{4,4}=\phi(6)$ 즉, 6과 서로소인 수의 개수가 되는 것이다. $A_{5,5}=\phi(9)=6$으로 잘 맞아 떨어진다. 대각화 과정을 전부 거치면 다음과 같이 된다.

\[=\begin{vmatrix} 1&1&1&1&1&1 \\ 0&1&0&1&0&1 \\ 0&0&2&2&2&2 \\ 0&0&0&2&0&2 \\  0&0&0&0&6&6 \\ 0&0&0&0&0&6 \\ \end{vmatrix}\]

집합의 원소가 몇 개가 되던 위의 논의를 확장할 수 있다. 따라서 행렬식의 값은 다음과 같다.

\[D_{n}=\prod_{x \in s} \phi(x)\]