시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 512 MB | 50 | 35 | 26 | 83.871% |
BOJ에서 어떤 문제를 풀었던 Sait2000은 입력 범위를 늘려서 장난 아니고 이산로그를 구해야 하는 문제를 만들기로 했습니다.
M = 1018 + 31은 소수이고, g = 42는 M의 원시근입니다. 즉, g1 mod M, g2 mod M ... gM - 1 mod M은 각각 서로 다른 [1; M) 범위의 정수입니다. f(x)를 gp mod M = x를 만족하는 최소의 양의 정수 p로 정의합니다. 그러면 f는 [1; M)에서 [1; M)으로 가는 전단사함수(일대일 대응)입니다.
수열 {an}을 다음과 같이 정의합니다.
n이 주어졌을 때, an을 찾아봅시다.
첫번째 줄에 정수 n이 주어집니다. (0 ≤ n ≤ 2 × 106)
an을 출력합니다.
0
960002411612632915
1
836174947389522544
300300
263358264583736303
1000000
300
1000001
60615953435770536