Editorial

---

D

summary:

길이 $1~n$의 배열 $a$에서 가능한 원소 $a_i(1\le a_i\le m,1-indexed)$들에 대해서

$gcd(i,a_i)=1$이어야 i번째 원소를 지울 수 있다.

지울 수 있는 인덱스가 $[1,1,1,\dots]$이 아닌 경우의 수를 구하라.

solution:

일단 모든 수열의 개수는 $m+m^2+m^3+\dots+m^n$이다.

거기서 지울 수 있는 인덱스가 전부 1(=$[1,1,1,\dots]$)인 경우의 수는 다음과 같다.

먼저, 결과 수열의 i번째 원소는 1~i까지의 수로 전부 다 나눠져야 한다.

왜냐하면 항상 첫 수만 지울 수 있어야 하기 때문에 처음에는 i로 나눠지면 안되고, 그 다음부터 앞의 모든 원소가 하나씩 제거되기 때문에 $a_i$가 잘리지 않으려면 차례로 $i-1,i-2,\dots,1$로 다 나눠져야 하기 때문이다.

그런데 수의 특성상 그 앞의 소수로만 모두 나눠지면 된다.

즉 1 이상 $x$ 이하 소수를 전부 곱한 값을 $f(x)$라고 하면, $a_i$는 $f(i)$의 배수여야 한다.

$f(i)$가 $m$을 넘으면 더 이상 곱할 필요가 없는데, 되는 수가 없기 때문이다.

정리하자면, i번째 수가 될 수 있는 수는 $m/f(i)$개 있고, $f(i)$가 m을 넘지 않을 때까지 i의 길이를 가진 지울 수 있는 인덱스가 전부 1(=$[1,1,1,\dots]$)인 수열의 개수를 구할 수 있으며 전체 경우의 수 $m+m^2+m^3+\dots+m^n$에서 그러한 경우를 빼 주면 된다.

opinion:

처음에는 지울 수 있는 인덱스가 전부 1(=$[1,1,1,\dots]$)을 구하려면 모두 안나눠져야 한다고 생각했다. 그래서 1~n까지 전부 서로소인 m이하 자연수 들을 전부 곱하면 될 것이라고 생각했는데, 이것은 구할 방법도 없을 뿐더러 틀린 생각이었다.

항상 첫번째 수만 제거되어야 하므로 i이하 소수에 대해 전부 나눠져야 하는 것이었다.

요새 이렇게 틀리는 문제가 많은데, 내가 지금 제대로 풀고 있는게 맞는지에 대한 생각을 할 필요가 있다.