[2731] 1379와 세제곱

2731번: 1379와 세제곱

 

뭔가 허무하게 풀리는 정수론 문제. 

우선 문제에서 준 네 수 1, 3, 7, 9를 살펴보자면,

$1^3\equiv 1\bmod 10$

$3^3\equiv 7\bmod 10$

$7^3\equiv 3\bmod 10$

$9^3\equiv 9\bmod 10$

이다. 따라서 $S \bmod 10$의 값으로 찾아야 하는 수 $x$의 첫째 자릿수를 구할 수 있다. ($x_1$)

이제 한 자리씩 $x$의 왼쪽에 붙이면서 수를 찾으면 되는데, 방법은 다음과 같다.

 

${x_n}^3 \bmod 10^{n+1} \equiv S \bmod 10^{n+1}$인 $n$자리 수 $x_n$을 생각한다. 이 때에 ${x_{n+1}}^3 \bmod 10^{n+2} \equiv S \bmod 10^{n+2}$을 어떻게 구할 수 있을지 알아보자.

정수 $m=\displaystyle\left\lfloor \frac{x_{n+1}}{10^{n+1}} \right\rfloor$을 생각하자. 이 때 $x_{n+1}=10^{n+1}m + x_n$이라 할 수 있다. 이 적절한 숫자 m을 구해야 한다. 양변을 세제곱하여 전개해 보자.

${x_{n+1}}^3$

$=(10^{n+1}m + x_n)^3$

$=10^{3n+3}m^3 + 3\cdot 10^{2n+2}m^2x_n + 3\cdot 10^{n+1}m{x_n}^2+{x_n}^3$

맨 아래 수식을 관찰해 보자. ${x_n}^3$에서 $n+1$번째 자리의 수를 변화시키기 위해서는 $10^{3n+3}m^3 + 3\cdot 10^{2n+2}m^2x_n + 3\cdot 10^{n+1}m{x_n}^2$의 $n+1$번째 자리 수, 즉

$10^{2n+2}m^3 + 3\cdot 10^{n+1}m^2x_n + 3m{x_n}^2 \equiv 3m{x_n}^2 \bmod 10$이 중요한 값이 된다.

 

따라서 ($3m{x_n}^2 \bmod 10$) + (${x_n}^3$의 $n+1$번째 자리 수)가 $S$의 $n+1$번째 자리 수가 되도록 하는 $m$을 찾으면 되고, $3{x_n}^3 \equiv c \bmod 10$, $\displaystyle\left\lfloor \frac{S}{10^{n+1}} \right\rfloor \equiv t \bmod 10$이라 할 때 $mc \equiv t \bmod 10$, $m \equiv tc^{-1} \bmod 10$이다.

 

여기서 $c$의 10에 대한 모듈러 역원은 항상 구할 수 있다. 앞서 $x_1$을 구할 때에 확인하였듯 $S \bmod 10 \in \{1, 3, 7, 9\}$이므로 또한 $x_1 \in \{1, 3, 7, 9\}$이기 때문에, $c \equiv 3{x_m}^3 \bmod 10 \equiv 3{x_1}^3 \bmod 10$ 이고, $\{3x^3 \bmod 10 |x\in \{1, 3, 7, 9\}\} = \{1, 3, 7, 9\}$이므로 가능한 $c$가 전부 10과 서로소이기 때문이다.

 

그럼 답은 $O(\log_{10} S)$만에 구할 수 있다.