[문제] 1이 될 때까지

# 2023.04.16
# 어떠한 수 N이 1이 될 때까지 두 과정중 하나를 반복적으로 선택하여 수행하려고 한다.
# 단 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.
# 1. N에서 1을 뺀다. / 2. N을 K로 나눈다.
# N과 K가 주어질 때, 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)

# 개선 답안
n, k = map(int,input().split())
count = 0
while n>=k: # n>=k일 때
    count+=n%k+1    # 나누고 남은 나머지(1씩 뻈다고 가정) + 1(나눗셈) 을 더함
    n//=k           # n 을 k로 나눈 몫으로 최신화
if (n!=1):  # n이 k보다 작아지면, 1이 될 때까지 빼는 횟수를 더해준다.
    count += n-1
print(count)