주기 없는 방문

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

요약

길이 N의 이진 문자열에서 각 새 문자는 문자열 끝이 어떤 블록을 K번 반복한 꼴일 때 1이 됩니다. 1의 개수를 구합니다.

문제

닉은 습관을 유지하는 데 늘 어려움을 겪는다. 어떤 행동을 $K$ 번 연속으로 하면 그 뒤로도 계속 하게 된다.

닉은 PBT(패턴 파괴 치료) 전문가인 패턴슨 박사를 매일 방문한다. 특정 날 방문했을 때 같은 행동을 $K$ 번 연속으로 했다면, 박사는 닉에게 요금을 청구한다.

PBT 덕분에 닉은 습관을 모두 끊었지만, 패턴슨 박사를 방문하는 습관만은 남아 있다. 잦은 방문으로 닉의 가계에 부담이 커지고 있다. 다음 $N$ 일 동안 닉이 박사에게 돈을 내야 하는 횟수를 구하라.

형식적으로, $s = s_1 s_2 s_3 \dots s_N$ 을 0과 1로 이루어진 문자열이라 하자. 이 문자열은 한 번에 한 글자씩 다음 규칙으로 만들어진다.

$i \leq K$ 이면 $s_i = 0$ 이다.
$i > K$ 이면, $s' = s_1 s_2 \dots s_{i-1}$ 이라 하자. $s'$ 의 끝 $|t| \cdot K$ 글자가 $t+t+\dots+t$ 로 쓸 수 있는 비어 있지 않은 문자열 $t$ 가 있으면 $s_i = 1$ 이다. 그렇지 않으면 $s_i = 0$ 이다.

$s_i = 1$ 은 $i$ 번째 날에 닉이 돈을 내야 함을 뜻한다. $s$ 에 있는 1의 개수를 구하라.

화난 얼굴 표시는 닉이 돈을 낸 날을 나타낸다.

한 줄에 정수 $N$ 과 $K$ 가 주어진다. ( $1 \leq N \leq 10^9$ , $2 \leq K \leq 10^9$ )

$s$ 에 있는 1의 개수를 나타내는 정수 하나를 출력한다.