%2021. 6. 29. 02:35에 작성된 글입니다%
https://www.acmicpc.net/problem/21094
21094번: Discrete Logarithm is a Joke
$M = 10^{18} + 31$ is a prime number. $g = 42$ is a primitive root modulo $M$, which means that $g^{1} \bmod M, g^{2} \bmod M, \ldots, g^{M-1} \bmod M$ are all distinct integers from $[1; M)$. Let's define a function $f(x)$ as the smallest positive integer
www.acmicpc.net
이산 로그 100만번 구하는건가보다 -> 그럴 리가! 님 낚임.
\( g^{a_{i+1}}\equiv a_i \mod M \)
여기서 \(a_{i+1}\)을 알면 \(a_i\)를 즉시 구할 수 있음을 캐치했다면 예제에 떡하니 박혀 있는 \(a_{1000000} = 300\)을 이용해서 쭉 내려가기...