non天平
题目背景
non 最近正在为自己的体重而苦恼,他想称量自己的体重。于是,他找来一个天平与许多砝码。
题目描述
砝码的重量均是 $n$ 的幂次,$n^1, n^2, n^3, n^4, n^5$ 的……non 想知道至少要多少个砝码才可以称出他的重量 $m$。注意砝码可以放左边,也可以放右边。
输入输出格式
输入格式
第一行一个正整数 $m$,表示 non 的重量;
第二行一个正整数 $n$,表示砝码重量幂次的底。
输出格式
一个整数表示最少所需的砝码数。
输入输出样例
输入样例 #1
99
10
输出样例 #1
2
说明
### 数据范围及约定
对于 $30\%$ 的数据点,$m \le 2^{63}-1$。
对于 $100\%$ 的数据点,$0 \le m \le 10^{10000}$,$0<n \le 10000$。