백준 21864번 - 이산로그가 장난이냐?

백준 21864번 문제 링크
문제 이름 : 이산로그가 장난이냐?
주 언어 : Python
태그 : 수학 / 정수론 / 런타임 전의 전처리 / 이산로그
solved.ac 등급 : Diamond II (2023/03/12 확인)

문제 보기

문제 :

BOJ에서 어떤 문제를 풀었던 Sait2000은 입력 범위를 늘려서 장난 아니고 이산로그를 구해야 하는 문제를 만들기로 했습니다.
$M = 10^{18} + 31$은 소수이고, $g = 42$는 $M$의 원시근입니다. 즉, $g^{1} \pmod{M}$, $g^2 \pmod{M}$, ..., $g^{M - 1} \pmod{M}$은 각각 서로 다른 [1; M) 범위의 정수입니다. $f(x)$를 $g^p \pmod{M} = x$를 만족하는 최소의 양의 정수 $p$로 정의합니다. 그러면 $f$는 [1; M)에서 [1; M)으로 가는 전단사함수(일대일 대응)입니다.
수열 $\left\{ a_{n} \right\}$을 다음과 같이 정의합니다.
$a_0 = 960002411612632915$
$a_{i + 1} = f\left(a_{i}\right)$
$n$이 주어졌을 때, $a_{n}$을 찾아봅시다.

입력 :

첫번째 줄에 정수 n이 주어집니다. ($0 ≤ n ≤ 2 \times 10^6$)

출력 :

$a_n$을 출력합니다.


참고자료 1
이 문제는 풀었으나, 풀이를 작성하고 있는 중입니다.
이산 로그 를 100만번 구하는 문제입니다.
원래는 그냥 무식하게 브루트포스로 구하려고 작정했으나, 이번 생에 안나올 것 같아서 포기했습니다.
일반 $\sqrt{N}$ 방법으로 100만번 구해서 시작해보려 했는데, 용량이 부족합니다. (10억개의 int가 있는 리스트...?)
그래서 참고자료 1을 기반으로 새로운 방식을 시도하고 있습니다.
예를 들어, $\operatorname{ind}_{42} 2 = 616320896497656200$, $\operatorname{ind}_{42} 3 = 216445357691997426$, $\operatorname{ind}_{42} 5 = 805764401374230400$ 을 기반으로, $300 = 2^2 \times 3 \times 5^2$이므로,
$\operatorname{ind}_{42} 300 = 616320896497656200 \times 2 + 216445357691997426 + 805764401374230400 \times 2 = 60615953435770536$으로 구할 수 있습니다.
$60615953435770536$은 2, 3, 5로만 나누어떨어지진 않는데 어떻게 해야할까요? 42씩 계속 곱해가면서 2, 3, 5로만 나누어 떨어지는 경우가 있는지 계속 찾아가면 됩니다.
$\operatorname{ind}_{42} \left(42^{s} \times t\right) = s + \operatorname{ind}_{42} t$ 이기 때문입니다.

$\operatorname{ind}_{42} 2 = 616320896497656200$는 어떻게 구한걸까요?
이산로그를 $y = g^k \pmod{p}$를 $O(\sqrt{p})$에 구하는 법은 다음과 같습니다.
1. $m = \lceil\sqrt{N}\rceil$을 정의한다.
2. 리스트 A = [$(y \times g^{-i}, i)$ for i in range(m)] 을 정의한다.
3. 리스트 B = [$(g^{mj}, mj)$ for j in range$\left(\lceil \frac{p}{m} \rceil + 1\right)$] 을 정의한다.
4. $A[i][0] = B[j][0]$이면, $\operatorname{ind}_{g} y = A[i][1] + B[j][1]$ 이다.
$y \times g^{-i} \equiv g^{mj} \pmod{p}$이면 $y \equiv g^{mj + i} \pmod{p}$이므로 가능한 알고리즘 입니다.
따라서, $2$부터 $1579$까지의 모든 소수에 대해 이산로그를 구해주고, 그걸 기반으로 10000 이하의 모든 소수에 대해 이산로그를 구해주고, 또 그걸 기반으로 100만번의 이산로그를 구했습니다.
1579까지의 모든 소수에 대해 이산로그를 구하는데 대략 25일이 걸렸는데, 더 효율적인 알고리즘으로 짜시면 분명히 이것보단 짧게 할 수 있습니다.
또, 100까지의 소수까지만 이산로그를 구해주고 그걸 기반으로 10000 이하의 모든 소수에 대한 이산로그를 구하시는걸 추천드립니다. (아마 그렇게 하는게 제일 빠를 것으로 생각됩니다.)

1602번째 푼 문제 (2023/03/12)
처음 푼 Diamond II 문제