P4988
ytb2024
·
·
题解
题目链接
题意：a_1 = 2，a_{n + 1} = \left( \sqrt [k] {a_n - n} + 2 \right) ^ k + n + 1，求最小整数 k 使得 a_n \equiv b \pmod m。
\begin{aligned}
a_{n + 1} &= \left( \sqrt [k] {a_n - n} + 2 \right) ^ k + n + 1
\\
a_{n + 1} - \left( n +1 \right) &= \left( \sqrt [k] {a_n - n} + 2 \right) ^ k
\\
\sqrt [k] {a_{n + 1} - \left( n +1 \right)} &= \sqrt [k] {a_n - n} + 2
\\
\sqrt [k] {a_{n + 1} - \left( n +1 \right)} - \sqrt [k] {a_n - n} &= 2
\end{aligned}
\texttt{令 } g \left( x \right) = \sqrt [k] {a_x - x}
\begin{aligned}
g \left( n + 1 \right) - g \left( n \right) &= 2
\\
g \left( n \right) - g \left( 1 \right) &= 2 \times \left( n - 1 \right)
\end{aligned}
\begin{aligned}
g \left( 1 \right) &= \sqrt [k] {a_1 - 1} = \sqrt [k] {1} = 1
\\
g \left( n \right) &= 2 \times n - 1
\end{aligned}
\begin{aligned}
\sqrt [k] {a_n - n} &= 2 \times n - 1
\\
a_n - n &= \left( 2 \times n - 1 \right) ^ k
\\
a_n &= \left( 2 \times n - 1 \right) ^ k + n
\end{aligned}
\begin{aligned}
a_n &\equiv b \pmod m
\\
\left( 2 \times n - 1 \right) ^ k + n &\equiv b \pmod m
\\
\left( 2 \times n - 1 \right) ^ k &\equiv b - n \pmod m
\end{aligned}