



# <문제> 1이 될 때까지


# 1. 문제 설명
# 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 함
# 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있음

# (1)번 연산 -> N에서 1을 뺌
# (2)번 연산 -> N을 K로 나눔

# 예를 들어 N이 17, K가 4라고 가정
# 이때 (1)번 연산의 과정을 한 번 수행하면 N은 16이 됨
# 이후에 (2)번 연산의 과정을 두 번 수행하면 N은 1이 됨
# 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 됨 -> N을 1로 만드는 최소 횟수

# N과 K가 주어질 때 N이 1이 될 때까지 (1)번 혹은 (2)번 의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성해라




# 2. 문제 조건
# 난이도 1, 풀이시간 15분, 시간제한 2초, 메모리 제한 128MB
# 입력 조건: 첫째 줄에 N(1<=N<=100000)과 K(2<=K<=100000)가 공백을 기준으로 하여 각각 자연수로 주어짐
# 출력 조건: 첫째 줄에 N이 1이될 때까지 (1)번 혹은 (2)번의 과정을 수행해야 하는 횟수의 최솟값을 출력




# 내가 짜본 코드  

n, k = map(int, input().split())
count = 0

while n != 1:
    if n % k == 0:
        n /= k
    else:
       n -= 1
    count += 1

print(count)

# 48 5  -> time: 2.3268492221832275
# 359 7 -> time: 4.6889708042144775





# 3. 문제 해결 아이디어
# 주어진 N에 대하여 최대한 많이 나누기를 수행하면 됨
# N의 값을 줄일 때 2이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있음




# 4. 정당성 분석 
# 가능하면 최대한 많이 나누는 작업이 최적의 해를 보장하는 이유는
# N이  아무리 큰 수여도, K로 계속 나눈다면 기하급수적으로 빠르게 줄일 수 있기 때문
# 즉, K가 2이상이기만 하면, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있음 
# 그리고 N은 항상 1에 도달하게 됨 -> 최적의 해 성립




# 5. 답안 예시  


# n, k를 공백 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True:
    # n이 k로 나누어 떨어지는 수가 될 때까지 빼기  -> (1)번 과정
    target = (n // k) * k  # target => 나누어 떨어지는 수
    result += (n - target) 
    n = target
    # n이 k보다 작을 때 (더 이상 나눌 수 없을 때) 빈복문 탈출
    if n < k:
        break
    # k로 나누기  -> (2)번 과정
    result += 1
    n //= k    

# 마지막으로 남은 수에 대하여 1씩 빼기  -> (1)번 과정
result += (n - 1)   
print(result)

# 48 5  -> time: 3.312412738800049
# 359 7 -> time: 3.3735320568084717


# 매 번 n을 확인해서 n이 k로 나누어 떨어진다면 (2)번 나누기 연산을 수행하고, 
# 그렇지 않다면 (1)번 빼기 연산을 수행하도록 하는 방식으로 간단하게 작성 할 수도 있지만  
# 위와 같이 작성한 이유는 반복문이 한 번 반복이 될 때마다 n이 k로 나누어지는 연산이 수행돼서
# 반복 횟수에 따라 기하급수적으로 n이 빠르게 줄어들게 되기 때문 
# -> 코드가 빨리 실행될 수 있도록 하여 log 시간 복잡도[O(logN)]가 나오도록 테크닉을 가미한 것 
# -> n과 k가 백억, 천억이 넘어가는 매우 큰 수일지라도 log 시간 복잡도로 빠르게 문제를 해결할 수 있음







