No.2122 Pseudorandom Number Generation with the Golden Ratio
p-adic
googol_S0
shino16Problem Statement
You are given as input a string $S$ of length $4$ consisting only of the characters $0$ to $9$, and non-negative integers $M,L$.
For a non-negative integer $m$, we call the following sequence of operations on a string $s$ of length $4$ consisting only of the characters $0$ to $9$ an $m$-shuffle:
- Let $n$ be the non-negative integer represented by $s$.
- Let $\alpha$ be the larger of the $2$ real solutions of the degree-$2$ equation $x^2 - nx - 1 = 0$, and let $D$ be its discriminant.
- Replace $s$ with the last $4$ digits of the integer part of $\frac{\alpha^m}{\sqrt{D}}$. (If the integer part of $\frac{\alpha^m}{\sqrt{D}}$ has only $3$ digits or fewer, prepend $0$ to pad it to $4$ digits.)
Find the string obtained by applying the $M$-shuffle to $S$ $L$ times.
Input
The input is given from standard input in the following format:
$S$ $M$ $L$
Constraints
The inputs $S,M,L $ satisfy the following constraints:
- $S$ is a string of length $4$ consisting only of the characters $0$ to $9$
- $M$ is a non-negative integer at most $10^{18}$
- $L$ is a non-negative integer at most $10^{18}$
Output
Output the string obtained by applying the $M$-shuffle to $S$ $L$ times, on $1$ line.
Print a newline at the end.
Sample
Sample 1
Input
0001 4 1
Output
0003
The non-negative integer $n$ represented by $S = 0001$ is $1$. The degree-$2$ equation
$\displaystyle x^2 - n x - 1 = 0 $
has the $2$ real solutions $\frac{1 \pm \sqrt{5}}{2}$, and the larger one, $\alpha$, is $\frac{1 + \sqrt{5}}{2} = 1.6 \cdots$, the value of the golden ratio. Since the discriminant $D$ is $n^2 + 4 = 5$, $\sqrt{D}$ is $\sqrt{5} = 2.2 \cdots$.
Since $\frac{\alpha^M}{\sqrt{D}} = \frac{\alpha^4}{\sqrt{D}} = 3.0 \cdots$, the last $4$ digits of its integer part are $0003$.
That is, applying the $M$-shuffle to $S = 0001$ gives $0003$, and since $L = 1$ here, the operations end at this point.
Sample 2
Input
0001 2 10
Output
0001
Since $S$ is the same as in Sample 1, $\alpha$ and $\sqrt{D}$ in the $1$st $M$-shuffle remain $\frac{1 + \sqrt{2}}{2} = 1.6 \cdots$ and $\sqrt{5} = 2.2 \cdots$, respectively.
However, since $\frac{\alpha^M}{\sqrt{D}} = \frac{\alpha^2}{\sqrt{D}} = 1.1 \cdots$, the last $4$ digits of its integer part are $0001$.
That is, applying the $M$-shuffle to $S = 0001$ leaves it as $0001$, and even after repeating the $M$-shuffle $L = 10$ times, it does not change from $0001$.
Sample 3
Input
0010 4 2
Output
0040
The non-negative integer $n$ represented by $S = 0010$ is $10$. The degree-$2$ equation
$\displaystyle x^2 - n x - 1 = 0 $
has the $2$ real solutions $5 \pm \sqrt{26}$, and the larger one, $\alpha$, is $5 + \sqrt{26} = 10.0 \cdots$. Since the discriminant $D$ is $n^2 + 4 = 104$, $\sqrt{D}$ is $\sqrt{104} = 10.1 \cdots$.
Since $\frac{\alpha^M}{\sqrt{D}} = \frac{\alpha^4}{\sqrt{D}} = 1020.0 \cdots$, the last $4$ digits of its integer part are $1020$.
That is, applying the $M$-shuffle to $S = 0010$ gives $1020$, and since $L = 2$ here, we apply the $M$-shuffle once more.
The non-negative integer $n$ represented by the replaced string $S = 1020$ is $1020$. The degree-$2$ equation
$\displaystyle x^2 - n x - 1 = 0 $
has the $2$ real solutions $510 \pm \sqrt{260101}$, and the larger one, $\alpha$, is $510 + \sqrt{260101} = 1020.0 \cdots$. Since the discriminant $D$ is $n^2 + 4 = 1040404$, $\sqrt{D}$ is $\sqrt{1040404} = 1020.0 \cdots$.
Since $\frac{\alpha^M}{\sqrt{D}} = \frac{\alpha^4}{\sqrt{D}} = 1061210040.0 \cdots$, the last $4$ digits of its integer part are $0040$.
That is, applying the $M$-shuffle to $S = 0010$ $L = 2$ times gives $0040$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。