%2021. 8. 22. 15:14에 작성된 글입니다%
https://www.acmicpc.net/problem/1160
1160번: Random Number Generator
첫째 줄에 6개의 정수 m, a, c, X0, n, g (m, a, c, X0, n ≤ 1018, g ≤ 108)가 차례대로 주어진다. a, c, X0는 음이 아닌 정수이고 m, n, g는 양의 정수이다.
www.acmicpc.net
\(X_{n+1}=aX_n+c \mod M\)
\(\mod M\)은 일단 나중에 계산하게 떼고 보면 다음과 같은 꼴이 된다.
\(X_{n+1}=aX_n+c\)
\(X_n\)의 일반항은
\(X_n=a^nX_0+c\left(1+a+...+a^{n-2}+a^{n-1}\right)\)
의 형태가 된다.
\(S\left(n\right)=\left(a^n,\ 1+a+...+a^{n-2}+a^{n-1}\right)\)
이렇게 \(S(n)\)을 정의하면
\(S\left(2n\right)\)
\(=\left(a^{2n},\ 1+a+...+a^{2n-2}+a^{2n-1}\right)\)
\(=\left(\left(a^n\right)^2,\ \left(a^n+1\right)\left(1+a+...+a^{n-2}+a^{n-1}\right)\right)\)
\(=\left(\left\{S\left(n\right)\left[0\right]\right\}^2,\ \left(S\left(n\right)\left[0\right]+1\right)\left(S\left(n\right)\left[1\right]\right)\right)\)
이렇게도 표현할 수 있다.
\(2n+1\)의 경우도 조금만 건드려 주면 되고
계산 과정 중에 모듈러 계속 때리는 것만 잊지 않으면 된다.
그러면 \(S(n)\)의 값을 \(O(\log n)\)만에 구할 수 있고
함수에서 마지막에 \(a^n\)의 값도 같이 뱉어주기 때문에
추가로 뭘 더 할 필요 없이 처리만 해서 출력하면 AC.
여담으로 처음에 시도할 때는 등비수열의 합 공식으로 접근했었는데, 모듈러 역원을 구하기 위해서는 \(a-1\)이 \(m\)과 서로소라야 한다는 조건 때문에 실패했다.