소개

이 기사에서는 ABC179에서 E 문제로 출제된 Sequence Sum이라는 문제에 대해 설명합니다.
기사를 쓰려고 생각한 동기로서는, 「왜 이번 수열에 주기성이 존재하는 것인가?」라고 의문으로 생각했기 때문입니다.
생각해 보면 주기성이 존재하는 것은 당연한 일입니다만, 제대로 설명하고 있는 기사가 현시점에서는 보이지 않았기 때문에 집필하기로 했습니다.

E - Sequence Sum에 등장하는 수열의 주기성

이 문제는 $A_{n+1} = {A_n}^2\\%\M$ 라는 숫자 열을 생각합니다.
이하, 이 수열이 주기성을 갖는다는 것을 나타냅니다.

문제의 링크입니다.
h tps // 아 t 여기 r. jp / sts / abc179 / sks / abc179_E

우선, 수열의 $i$ 항목을 $A_i$로 합니다.
그러면 Mod의 정의보다 다음을 알 수 있습니다.

0 \leqq\ {A_i}^2 \% M\ \leqq M-1\\
\Leftrightarrow 0 \leqq A_{i+1} \leqq M-1

이 부등식으로부터는 수열의 어느 항도 $0$ 이상 $(M-1)$ 이하의 값, 즉 $M$ 거리의 값 밖에 취하지 않는다는 것을 알 수 있습니다.

그런 다음 첫 번째 항을 $A_1$로 시작하고 첫 번째 $M$ 항인 $A_M$까지 수열 값을 찾았다고 가정합니다.
이때 제$1$항에서 제$M$항까지 벗어나, 즉 $A_i\neq A_j,\(1\leqq i,j\leqq M)$이었다고 합니다.


여기서, $M+1$ 항목인 $A_{M+1}$를 구하면, 수열의 값은, 위에서 말한 바와 같이 $M$대로 밖에 없기 때문에, 지금까지 구한 값 $A_i $와 일치합니다.


위의 설명에서 수열을 유향 그래프로 하면 다음과 같이 사이클이 존재하는 그래프로 나타낼 수 있습니다.


이상으로부터, $1\leqq i

수열의 값을 점점 구해 가면, 언젠가 루프하기 시작한다는 것이 위의 그림에서 알 수 있다고 생각합니다.
따라서 이번 수열에는 주기성이 존재하는 것으로 나타났습니다.

결론

아직 수행중인 몸이므로, 실수와 이해하기 어려운 표현이 있으면 꼭 가르쳐 주시면 기쁩니다.
만약 이 기사의 내용이 도움이 되면 LGTM을 해 주시면 모티베로 연결됩니다.
읽어 주셔서 감사합니다.