K번째 자리 숫자

시간 제한1초메모리 제한1024 MB

요약

X = A + √B이고 |A - √B| < 1일 때, N이 10^9까지, K가 4까지 주어질 때 floor(X^N)의 K번째 최하위 자릿수를 구한다.

난이도: 보통10점 중 7점
유형: 수학, 정수론, 행렬, 동적 계획법
정답자: 아직 제출이 없습니다

문제

실수 $X$ 가 $X = A + \sqrt{B}$ 꼴로 주어진다. $A$ 와 $B$ 는 양의 정수이고 $-1 < A - \sqrt{B} < 1$ 을 만족한다. 정수 $N$ 과 $K$ 가 함께 주어질 때, $\lfloor X^N \rfloor$ 의 아래에서 $K$ 번째 자리 숫자를 구하여라. 예를 들어 $K = 1$ 이면 $\lfloor X^N \rfloor$ 의 일의 자리 숫자를 구하면 된다. $\lfloor X^N \rfloor$ 의 자릿수가 $K$ 보다 적으면 $K$ 번째 자리 숫자는 0으로 본다.

입력

첫째 줄에 정수 $A$ , $B$ , $N$ , $K$ 가 공백으로 구분되어 주어진다. $1 \le A, B \le 10^4$ , $1 \le N \le 10^9$ , $1 \le K \le 4$ 이고, 입력은 항상 $-1 < A - \sqrt{B} < 1$ 을 만족한다.

출력

$\lfloor X^N \rfloor$ 의 아래에서 $K$ 번째 자리 숫자를 한 줄에 출력한다.

예제4

예제 1
입력
```
3 10 1 1
```
예상 출력
```
6
```
예제 2
입력
```
3 10 2 1
```
예상 출력
```
7
```
예제 3
입력
```
3 10 1000000000 1
```
예상 출력
```
1
```
예제 4
입력
```
10 90 1000000000 2
```
예상 출력
```
9
```