만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

감옥

시간 제한2초메모리 제한512 MB

요약

무한한 수열에서 k의 배수를 반복해서 제거하고 다시 번호를 매기는 과정을 거친 뒤, N번째 단계에서 석방되는 죄수의 원래 번호를 구한다.

난이도: 어려움10점 중 8점
유형: 수학, 조합론, 시뮬레이션, 정수론
정답자: 아직 제출이 없습니다

문제

무한히 많은 죄수가 있다. 처음에 죄수들은 $0,\ 1,\ 2,\ ...$ 번호가 붙어 있다.

다음 작업을 $N$ 번 수행한다.

$0$ 번 죄수를 석방하고, $k,\ 2k,\ 3k,\ ...$ 번 죄수들을 처형한다.
그 뒤 남은 죄수들에게 번호를 다시 붙인다. 이때 원래 번호가 작은 죄수부터 $0,\ 1,\ 2,\ ...$ 번호를 붙인다.

$N$ 번째 작업에서 석방되는 죄수가 처음에 붙어 있던 번호를 구하여라.

입력

입력은 다음 형식으로 표준 입력에서 주어진다.

$N$ $k$

출력

답을 한 줄에 출력한다.

제한

$1\leq N\leq10^5$
$2\leq k\leq10^5$
답은 $10^{18}$ 이하이다.

예제3

예제 1
입력
```
4 2
```
예상 출력
```
7
```
예제 2
입력
```
1 3
```
예상 출력
```
0
```
예제 3
입력
```
100000 100000
```
예상 출력
```
99999
```

Loading...