306296: CF1175A. From Hero to Zero
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
From Hero to Zero
题意翻译
给整数 $n,k$,每次你可以做如下两个操作之一 - 将 $n$ 减 $1$ - 将 $n$ 除以 $k$ (前提:$n$ 是 $k$ 的倍数) 试求让 $n$ 变为 $0$ 的最小操作次数。题目描述
You are given an integer $ n $ and an integer $ k $ . In one step you can do one of the following moves: - decrease $ n $ by $ 1 $ ; - divide $ n $ by $ k $ if $ n $ is divisible by $ k $ . For example, if $ n = 27 $ and $ k = 3 $ you can do the following steps: $ 27 \rightarrow 26 \rightarrow 25 \rightarrow 24 \rightarrow 8 \rightarrow 7 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0 $ . You are asked to calculate the minimum number of steps to reach $ 0 $ from $ n $ .输入输出格式
输入格式
The first line contains one integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of queries. The only line of each query contains two integers $ n $ and $ k $ ( $ 1 \le n \le 10^{18} $ , $ 2 \le k \le 10^{18} $ ).
输出格式
For each query print the minimum number of steps to reach $ 0 $ from $ n $ in single line.
输入输出样例
输入样例 #1
2
59 3
1000000000000000000 10
输出样例 #1
8
19