[3752] 최대공약수 행렬식

문제 링크 : https://www.acmicpc.net/problem/3752

3752 - 최대공약수 행렬식

본문

집합 $S = \lbrace x_1, x_2, \cdots, x_n \rbrace$가 인수에 대해서 닫혀있으려면, 모든 $x_i \in S$에 대해서, $x_i$의 모든 약수 $d$는 $d \in S$를 만족해야 한다.

인수에 대해 닫힌 집합 $S$를 최대공약수 행렬 $(S) = (s_{ij})$, $s_{ij} = \text{GCD}(x_i,x_j)$로 만든 뒤, 이 행렬의 행렬식 (determinant)를 구하는 프로그램을 작성하시오.

\[D_n = \begin{bmatrix} \text{gcd}\left(x_1,x_1\right) & \text{gcd}\left(x_1,x_2\right) & \text{gcd}\left(x_1,x_3\right) & \dots & \text{gcd}\left(x_1,x_n\right) \\ \text{gcd}\left(x_2,x_1\right) & \text{gcd}\left(x_2,x_2\right) & \text{gcd}\left(x_2,x_3\right) & \dots & \text{gcd}\left(x_2,x_n\right) \\ \text{gcd}\left(x_3,x_1\right) & \text{gcd}\left(x_3,x_2\right) & \text{gcd}\left(x_3,x_3\right) & \dots & \text{gcd}\left(x_3,x_n\right) \\ \dots & \dots & \dots & \dots & \dots \\ \text{gcd}\left(x_n,x_1\right) & \text{gcd}\left(x_n,x_2\right) & \text{gcd}\left(x_n,x_3\right) & \dots & \text{gcd}\left(x_n,x_n\right) \\ \end{bmatrix}\]

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 집합 $S$의 원소 개수 $n(0 < n < 1,000)$이 주어진다.

다음 줄에는 집합의 원소 $x_1, x_2, \cdots, x_n$이 주어진다. ($0 < x_i < 2 \times 10^9$, $x_i$는 정수)

출력

각 테스트 케이스에 대해서 입력으로 주어진 집합 S의 최대공약수 행렬식을 $1000000007$ ($10^{9}+7$)로 나눈 나머지를 출력한다.

제한

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

• $0 < N < 1000$
• $0 < x_i < 2 \times 10^{9}$

---

풀이

이론 수립

행렬의 행렬식, 대학교 수업에서 배웠던 내용이다. 하지만 수업에서 배웠던 행렬식 계산법은 2x2 크기의 정사각형 행렬에 대한 공식이고, 그것보다 큰 행렬의 행렬식은 재귀적으로 크기가 1 작은 행렬의 행렬식을 구하고 계속해서 이용하는 방법이었다. 이 문제에서 만들어지는 행렬의 크기는 최대 999x999 크기이므로, 2x2 크기의 행렬식을 계산하는 함수를 $\frac{999!}{2}$ 번 수행해야할 것이다. 뭐.. 할 수 있으면 해보는 것을 추천한다 :)

이 문제를 해결할 실마리는 대학원 수업에서 들었던 내용이다. 사용할 수 있는 방법은 ‘삼각행렬의 leading entry들의 곱으로 determinant를 계산할 수 있다’는 점이다. 문제에서 주어지는 행렬을 삼각행렬로 변형시킬 수 있다면 계산을 쉽게 할 수 있을 것이다. (사실 삼각행렬을 이용한 행렬식 계산 방법만을 알고있어서, 문제 해결 방법을 행렬을 강제로 변형시키는 것으로 선택했다.) 문제에 대해 이해하기 전에, 문제에서 사용할 수 있을만한 determinant의 유용한 정보에 대해 기록해두자. 이것은 사용할 수도 있고 사용하지 않을 수도 있다.

• 삼각행렬이 주어졌다면 그의 대각원소의 곱으로 행렬식을 구할 수 있다.
• 행렬에서, 임의의 행에 다른 임의의 행을 빼는 연산을 수행해도 행렬식 값은 변하지 않는다. ( det(B) = det(A) )
• 행렬에서, 임의의 두 행의 위치를 바꾸는 연산은 행렬식의 부호를 바꾼다. ( det(B) = -det(A) )
• 행렬에서, 임의의 행에 어떤 수 $k$를 곱한다면, 행렬식의 값도 $k$배 증가한다. ( det(B) = k x det(A) )

자, 그럼 행렬을 어떻게 삼각행렬로 바꿀 수 있을까? 당장은 규칙이 보이지 않으니 예제를 찾아보자. 문제에서 제공하는 예제는 너무 작아서, 괜찮은 예제를 하나 가져와서 사용해보자. 이번 풀이에서 사용해볼 예제는 $S = \lbrace 1, 2, 3, 4, 6, 8, 12\rbrace$ 로 사용할 것이다. 집합 $S$를 이용하여 만들 수 있는 행렬은 아래와 같다.

\[\begin{align} D = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 1 & 2 & 2 & 2 & 2 \\ 1 & 1 & 3 & 1 & 3 & 1 & 3 \\ 1 & 2 & 1 & 4 & 2 & 4 & 4 \\ 1 & 2 & 3 & 2 & 6 & 2 & 6 \\ 1 & 2 & 1 & 4 & 2 & 8 & 4 \\ 1 & 2 & 3 & 4 & 6 & 4 & 12 \\ \end{bmatrix} \end{align}\]

이 때 행렬의 원소를 표기하는 것으로 $D_{a, b}$를 사용할 것이다. 이 때 $a, b$는 편의상 index가 아니라 집합 $S$에서 사용했던 원소값을 사용할 것이다. 삼각행렬로 만들기 위해, 먼저 첫 줄을 다른 모든 행에서 빼주도록 하자. 이 연산은 행렬식에 영향을 주지는 않는다.

\[\begin{align} D = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 2 & 0 & 2 & 0 & 2 \\ 0 & 1 & 0 & 3 & 1 & 3 & 3 \\ 0 & 1 & 2 & 1 & 5 & 1 & 5 \\ 0 & 1 & 0 & 3 & 1 & 7 & 3 \\ 0 & 1 & 2 & 3 & 5 & 3 & 11 \\ \end{bmatrix} \end{align}\]

대각선 요소만 보면, $D_{2,2}$는 1로, $D_{3,3}$는 2로 바뀐 것을 알 수 있다. 한번만 더 진행해보자. 이번에는 2번째 행에 대한 연산을 진행한다. 첫줄은 이미 연산을 진행해서 leading entry의 값이 바뀌지는 않으니까, 빼고 계산한다.

\[\begin{align} D = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 2 & 0 & 2 & 0 & 2 \\ 0 & 0 & 0 & 2 & 0 & 2 & 2 \\ 0 & 0 & 2 & 0 & 4 & 0 & 4 \\ 0 & 0 & 0 & 2 & 0 & 6 & 2 \\ 0 & 0 & 2 & 2 & 4 & 2 & 10 \\ \end{bmatrix} \end{align}\]

이제는 $D_{3,3}$은 2로, $D_{4,4}$도 2로 바뀐 것을 알 수 있다. 이쯤에서 알 수 있는 것은, 만약 집합의 원소들이 오름차순으로 정렬되어있다면, ‘GCD는 두 수보다 항상 작거나 같다’는 점을 이용하여 row reduction을 수행한다고 해도 행렬의 대각원소는 항상 0이 아님을 보장할 수 있다. 따라서 주어지는 행렬을 삼각행렬로 항상 만들 수 있고, 그렇다면 행렬식 구하기는 쉬울 것이다. 일단 주어진 행렬을 삼각행렬로 만들어보자.

\[\begin{align} D_t = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 2 & 0 & 2 & 0 & 2 \\ 0 & 0 & 0 & 2 & 0 & 2 & 2 \\ 0 & 0 & 0 & 0 & 2 & 0 & 2 \\ 0 & 0 & 0 & 0 & 0 & 4 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 4 \\ \end{bmatrix} \end{align}\]

이렇게 되면 이 문제에서의 행렬식은 각 대각원소의 곱인 $128$로 계산할 수 있다. 근데, 이 문제에서 주어지는 행렬은 최대 1000개의 행을 가지고 있다. 이걸 1초 안에 돌리기는 힘들 것이다. 대각원소를 row reduction 연산을 하지 않고 구할 수 있는 방법이 있을까?

삼각행렬 $D_t$에서 가장 마지막 원소, $D_{12, 12}$를 보자. 원래는 $12$였는데 최종 삼각행렬에서는 $4$로 줄어듬을 알 수 있다. 이 값만 관찰하면서 방법을 찾아보자. 문제에서 제시한 조건으로 $D_{a, a} = \text{GCD(a, a)}$이므로, $D_{a,a} = a$임을 알 수 있다. 그래서 처음 상황에서 $D_{12, 12} = 12$라고 할 수 있겠다. 이후 첫 row reduction 연산에서, 우리는 $D_{12, 12}$에 $D_{1, 12}$를 빼게 된다. 두번째 row reduction 연산에서는 $D_{12,12}$에서 $D_{2,12}$를 빼게 된다. 그 이후 연산에서도 $D_{12, 12}$에는 다른 수들의 영향을 받아 빼는 과정이 반복된다. 단 하나, $D_{8, 12}$에서는 그 과정이 진행되지 않는다. 그렇게, $D_{12,12}$에 영향을 준 원소값의 행 번호를 살펴보면 $\lbrace 1, 2, 3, 4, 6 \rbrace$임을 알 수 있다. 그리고 놀랍게도, 이것은 $12$의 약수이다.

사실 아직 이해가 안된다. $D_{12,12}$에 특정 값들이 어떻게 영향을 주는지 파악해보자. 아래는 그 순서이다.

• $1$을 원소로 하는 행이 row reduction을 수행한다. 모든 행에 대해 $D_{1, x}$가 영향을 미쳤다.
  • 이 때 이전의 모든 영향을 받은 $D_{1,12}$의 값은 $D_{1,12}$이다.
  • $D_{2, 12}$에 $D_{1, 12}$가 빼졌다. (이후 이 상황을 $D_{2, 12} - D_{1, 12}$라고 할 것이다.)
  • 각각의 수들은 $D_{3, 12} - D_{1, 12}$, $D_{4, 12} - D_{1, 12}$, $D_{6, 12} - D_{1, 12}$, $D_{8, 12} - D_{1, 12}$, $D_{12, 12} - D_{1, 12}$로 영향을 받는다.
• $2$를 원소로 하는 행이 row reduction을 수행한다. 모든 행에 대해 $D_{2, x}$가 영향을 미쳤다.
  • 이 때 이전의 모든 영향을 받은 $D_{2, 12}$의 값은 $D_{2, 12} - D_{1, 12}$이다.
  • 그런데 $D_{2, x}$가 $D_{3, x}$에는 영향을 주지 못했다.
  • 각각의 수들은 $D_{4, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12})$, $D_{6, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12})$, $D_{8, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12})$, $D_{12, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12})$로 영향을 받는다.
• $3$을 원소로 하는 행이 row reduction을 수행한다. 모든 행에 대해 $D_{3, x}$가 영향을 미쳤다.
  • 이 때 이전의 모든 영향을 받은 $D_{3, 12}$의 값은 $D_{3, 12} - D_{1, 12}$이다.
  • 그런데 $D_{3, x}$가 $D_{4, x}, D_{8, x}$에는 영향을 주지 못했다.
  • 각각의 수들은 $D_{6, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12}) - (D_{3, 12} - D_{1, 12})$, $D_{12, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12}) - (D_{3, 12} - D_{1, 12})$로 영향을 받는다.
• $4$를 원소로 하는 행이 row reduction을 수행한다. 모든 행에 대해 $D_{4, x}$가 영향을 미쳤다.
  • 이 때 이전의 모든 영향을 받은 $D_{4,12}$의 값은 $D_{4, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12})$이다.
  • 그런데 $D_{4,x}$가 $D_{6,x}$에는 영향을 주지 못했다.
  • 각각의 수들은 $D_{8, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12}) - (D_{4, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12}))$, $D_{12, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12}) - (D_{3, 12} - D_{1, 12}) - (D_{4, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12}))$로 영향을 받는다.
• $6$을 원소로 하는 행이 row reduction을 수행한다. 모든 행에 대해 $D_{6,x}$가 영향을 미쳤다.
  • 이 때 이전의 모든 영향을 받은 $D_{6,12}$의 값은 $D_{6, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12}) - (D_{3, 12} - D_{1, 12})$이다.
  • 그런데 $D_{6,x}$가 $D_{8,x}$에는 영향을 주지 못했다.
  • 각각의 수들은 $D_{12, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12}) - (D_{3, 12} - D_{1, 12}) - (D_{4, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12})) - (D_{6, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12}) - (D_{3, 12} - D_{1, 12}))$로 영향을 받는다.
• $8$을 원소로 하는 행이 row reduction을 수행한다. 모든 행에 대해 $D_{8,x}$가 영향을 미쳤다.
  • 이 때 이전의 모든 영향을 받은 $D_{8,12}$의 값은 $D_{8, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12}) - (D_{4, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12}))$이다.
  • 그런데 $D_{8,x}$가 $D_{12,x}$에는 영향을 주지 못했다.
• 마지막 남은 $12$를 원소로 하는 행이 row reduction을 수행한다. 변화는 없다.
  • 이 때 이전의 모든 영향을 받은 $D_{12,12}$의 값은 $D_{12, 12} - (D_{1, 12}) - (D_{2, 12} - D_{1, 12}) - (D_{3, 12} - D_{1, 12}) - (D_{4, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12})) - (D_{6, 12} - D_{1, 12} - (D_{2, 12} - D_{1, 12}) - (D_{3, 12} - D_{1, 12}))$이다.

막상 순서를 그렸는데 수식이 너무 길다. 이번에는 표로 그려보자. 이 표는 행렬의 원소 $D_{x,12}$의 상태를 나타낸다. 첫 상태는 표 normal과 같다.

normal	1,12	2,12	3,12	4,12	6,12	8,12	12,12
0.5
1							O
1.5						O
2					O		O
2.5
3				O		O	O
3.5
4			O		O		O
4.5						O
5							O
5.5
6		O		O	O	O	O
6.5
7							O
7.5						O
8			O		O		O
8.5
9				O		O	O
9.5
10					O		O
10.5						O
11							O
11.5
12	O	O	O	O	O	O	O
sum = $D_{x, 12}$	1	2	3	4	6	8	12

다음 표 row1은 $1$을 원소로 하는 행의 row reduction을 진행한 이후를 보인다. 이곳에서는 $\lbrace 2, 3, 4, 6, 8, 12\rbrace$의 $D$값에 대한 변화가 있었다. 본인 행의 원소에는 영향을 주지 않는다. 삼각행렬로 생각해보면 이미 값이 확정되었기 때문이다. 이 값은 sum 행에서 굵은 글씨체로 표시하겠다.

row1	1,12	2,12	3,12	4,12	6,12	8,12	12,12
0.5
1							O
1.5						O
2					O		O
2.5
3				O		O	O
3.5
4			O		O		O
4.5						O
5							O
5.5
6		O		O	O	O	O
6.5
7							O
7.5						O
8			O		O		O
8.5
9				O		O	O
9.5
10					O		O
10.5						O
11							O
11.5
12	O
sum = $D_{x, 12}$	1	1	2	3	5	7	11

다음 표 row2는 $2$를 원소로 하는 행의 row reduction을 진행한 이후를 보인다. 이곳에서는 $\lbrace 4, 6, 8, 12\rbrace$의 $D$값에 대한 변화가 있었다.

row2	1,12	2,12	3,12	4,12	6,12	8,12	12,12
0.5
1							O
1.5						O
2					O		O
2.5
3				O		O	O
3.5
4			O		O		O
4.5						O
5							O
5.5
6		O
6.5
7							O
7.5						O
8			O		O		O
8.5
9				O		O	O
9.5
10					O		O
10.5						O
11							O
11.5
12	O
sum = $D_{x, 12}$	1	1	2	2	4	6	10

이제 뭔가 보이기 시작한다. 계속 진행해보자.

row3	1,12	2,12	3,12	4,12	6,12	8,12	12,12
0.5
1							O
1.5						O
2					O		O
2.5
3				O		O	O
3.5
4			O
4.5						O
5							O
5.5
6		O
6.5
7							O
7.5						O
8			O
8.5
9				O		O	O
9.5
10					O		O
10.5						O
11							O
11.5
12	O
sum = $D_{x, 12}$	1	1	2	2	2	6	8

row4	1,12	2,12	3,12	4,12	6,12	8,12	12,12
0.5
1							O
1.5						O
2					O		O
2.5
3				O
3.5
4			O
4.5						O
5							O
5.5
6		O
6.5
7							O
7.5						O
8			O
8.5
9				O
9.5
10					O		O
10.5						O
11							O
11.5
12	O
sum = $D_{x, 12}$	1	1	2	2	2	4	6

row6	1,12	2,12	3,12	4,12	6,12	8,12	12,12
0.5
1							O
1.5						O
2					O
2.5
3				O
3.5
4			O
4.5						O
5							O
5.5
6		O
6.5
7							O
7.5						O
8			O
8.5
9				O
9.5
10					O
10.5						O
11							O
11.5
12	O
sum = $D_{x, 12}$	1	1	2	2	2	4	4

row8	1,12	2,12	3,12	4,12	6,12	8,12	12,12
0.5
1							O
1.5						O
2					O
2.5
3				O
3.5
4			O
4.5						O
5							O
5.5
6		O
6.5
7							O
7.5						O
8			O
8.5
9				O
9.5
10					O
10.5						O
11							O
11.5
12	O
sum = $D_{x, 12}$	1	1	2	2	2	4	4

row12	1,12	2,12	3,12	4,12	6,12	8,12	12,12
0.5
1							O
1.5						O
2					O
2.5
3				O
3.5
4			O
4.5						O
5							O
5.5
6		O
6.5
7							O
7.5						O
8			O
8.5
9				O
9.5
10					O
10.5						O
11							O
11.5
12	O
sum = $D_{x, 12}$	1	1	2	2	2	4	4

규칙이 보이는가? $D_{12,12}$에서 남은 수들이 무엇인가? $\lbrace 1, 5, 7, 11\rbrace$.. 놀랍게도 이들은 12의 서로소들이다. 실제로, 예시에서 만들었던 삼각행렬에 존재하는 원소들 $\lbrace 1, 1, 2, 2, 2, 4, 4 \rbrace$는 각각 닫힌 집합 $S$의 원소들인 $\lbrace 1, 2, 3, 4, 6, 8, 12\rbrace$들의 본인보다 작은 서로소인 정수의 개수이다. 여기까지 정말 오래 걸렸지만, 대각원소의 규칙을 찾았으니 row reduction을 진행하지 않아도 대각원소를 구할 수 있을 것이다. 근데.. 서로소의 개수는 어떻게 구할 수 있을까..?

예전에 다른 문제를 풀다가 얼핏 봤던 함수가 있다. 바로 오일러 피 함수 $\phi(n)$이다. 이 함수 자체가 ‘$[1, n]$ 범위에서 $n$과 서로소인 정수의 개수’를 반환한다. 이것을 구현할 수 있다면 답을 구할 수 있다는 것이다. 일반적으로 아래와 같음이 알려져있다.

• 소수 $p$에 대해 $\phi(p) = p-1$이다.
  • 그리고, 소수 $p$의 거듭제곱 $p^k$에 대해 $\phi(p^k) = p^{k-1}(p-1)$이다.
• 두 서로소 $m, n$에 대해 $\phi(mn) = \phi(m) \phi(n)$이다.
• 위 2개를 이용하여, 어떤 정수 $n$을 나누어 떨어지게 할 수 있는 소수들 $p$에 대해, $\phi(n) = \underset{p \vert n }{\Pi} (p - 1)$이다. 이 때 $p$는 중복이 가능하다.

그러면 문제에서 원하는 임의의 수를 특정 범위까지 확실하게 나눌 수 있는 소인수가 무엇인지 미리 알아두면 모든 수에 대해 $\phi(n)$의 값을 계산할 수 있을 것이다. 이것으로 대각원소 값을 구하는 것은 해결할 수 있을 것이다.

하지만 아직도 문제가 몇개 더 남았다. 방금 나온 ‘미리 기록해야하는 가장 큰 소수가 몇인가?’와 맨 처음에 가정했던 ‘닫힌 집합 $S$의 모든 원소가 오름차순으로 정렬되어있다는 가정’이다. 이것을 해결할 수 있으면 문제에서 원하는 해답을 얻을 수 있을 것이다.

• Q. 미리 기록해야하는 가장 큰 소수가 몇인가?

  • 입력받을 수 있는 원소의 최댓값은 $2 \times 10^{9} - 1$이다. 특정 수가 소수인지 판단하기 위해서는 그 수의 제곱근까지의 소수까지만 탐색하면 그 수가 소수인지 판단이 가능하다. 그러므로, 입력으로 받을 수 있는 최댓값의 제곱근인 $44721$까지만 소수 판별을 진행하면 된다.

• Q. 닫힌 집합 $S$의 모든 원소를 어떻게 하면 오름차순으로 정렬되어있다는 가정으로 바꿀 수 있을까?

  • 사실 아무 의미가 없는 고민이다. 일반적으로 2x2 크기의 행렬에서, 행렬식을 계산하는 공식은 아래와 같다.

    \[D = \begin{bmatrix} a & b \\ c & d \end{bmatrix}, det(D) = ad-bc\]

    예시로 $S_1 = \lbrace 1, 2 \rbrace$와 $S_2 = \lbrace 2, 1 \rbrace$인 두 집합이 있다고 생각하면 두 집합으로 만들 수 있는 행렬값은 부호가 반대일 것 같다. 하지만 막상 행렬을 만들어보면 아래와 같다.

    \[S_1 = \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}, S_2 = \begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix}\]

    그런데, 2x2 크기의 행렬에 대한 행렬식 공식에 의해 $det(S_1) = det(S_2) = 1$이다. 즉, 집합의 원소가 어떤 순서로 있더라도 행렬식 값이 변하지 않는다.

자, 이론은 다 갖추었다. 이것을 구현해보자!

1차 수정본

구현 결과는 시간초과, 아무래도 오일러 phi 함수 구현에서 시간이 많이 잡아먹히는 것 같다. 현재 작성한 함수는 아래와 같다.

int phiFunc(int x) {
    int r = 1;
    for (int i = 2; i < MAX_SQRT; ++i) {
        if (i >= x) {
            break;
        }

        int k = 0;
        int p = 1;
        while (x % i == 0) {
            ++k, p *= i;
            x /= i;
        }
        if (k > 0) {
            p /= i;
            r *= (p * (i - 1));
        }
    }
    if (x != 1) {
        r *= (x - 1);
    }
    return r;
}

2부터 44721까지, 반복하며 결과를 추론하는 방법이다. 생각해보면 이 방법은 $O(\sqrt{x})$, 이게 결국 테스트케이스당 ‘숫자 1000개 $\times$ 각 원소의 최악 탐색횟수 44720번’ 연산을 수행하여 약 4500만번의 연산을 수행하는 것 같다. 이러면 당연히 1초 안에는 돌지 않는다. 다른 곳에서는 시간을 줄일 방법이 없어서, 이 부분에서 탐색을 줄여야한다.

추가로 사용할 수 있는 정보가 무엇이 있을까? 문제를 다시 읽어보니 문제에서 사용한 집합은 닫힌 집합이라고 한다. 닫힌 집합은 ‘모든 원소에 대해서 그 약수들이 모두 집합에 속해있다’는 집합이라고 한다. 그러면, 한가지 활용할 수 있는 항등식이 있다.

\[\sum_{d \vert n} \phi(d) = n\]

위 식은 ‘어떤 수 $n$의 모든 약수들의 $\phi$ 함수값의 합은 그 수 $n$과 같다’를 나타내는 수식이다. 생각해보면 이미 어떤 수 $n$의 약수가 모두 집합 $S$ 안에 존재하므로, 그들의 값을 모두 구했다면 $\phi(n)$의 값도 바로 구할 수 있다는 얘기이다. 이 방법을 사용하면 각 수에 대해서 $O(N)$이면 $\phi$값을 구할 수 있다. $N$의 최댓값이 1000인 것을 감안하면, 4500만번의 연산을 50만번의 연산으로 줄일 수 있다!

원소의 순서는 바뀌어도 상관없음을 보였으므로, 입력받은 원소들을 오름차순으로 정렬하자. 어짜피 집합의 원소에는 $1$이 존재할 것이므로, $\phi(1) = 1$로 일단 고정하고 시작하자. 이후 다른 원소 $x$는 이전까지의 원소들을 이용하여 $x$를 이전의 원소로 나누어 떨어지게 할 수 있는지 확인하고, 만약 그럴 수 있다면 그 $\phi$값을 찾아두었다가 마지막에 사용하여 $\phi(x)$를 구하고, 그 값을 저장해두도록 하자.

• 참고 알고리즘 : 삼각행렬, 오일러 phi 함수

코드

사용 언어 : C

최종 수정일 : 2023 / 1 / 15

#include <stdio.h>

typedef long long ll;

typedef struct IntPhi {
    int n;
    int phi;
} IP;

#define MOD (int)(1e9 + 7)
#define MAX_IDX 1000

int cmp(IP* a, IP* b) {
    return a->n > b->n;
}

int main() {
    int t;
    scanf("%d", &t);

    while (t--) {
        IP arr[MAX_IDX];
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            int x;
            scanf("%d", &x);
            arr[i] = (IP){x, 0};
        }

        qsort(arr, n, sizeof(IP), cmp);
        arr[0].phi = 1;     // phi(1)

        ll retval = 1;
        for (int i = 1; i < n; ++i) {
            int temp = 0;
            for (int j = 0; j < i; ++j) {
                if (arr[i].n % arr[j].n == 0) {
                    temp += arr[j].phi;
                }
            }
            arr[i].phi = arr[i].n - temp;
            retval *= arr[i].phi, retval %= MOD;
        }

        printf("%lld\n", retval);
    }
    return 0;
}

• arr[] : 입력과 그에 상응하는 $\phi$값을 기록
• retval : 문제에서 원하는 행렬식을 기록, 매 연산마다 mod 연산을 수행해야한다.