#P16944. [sgu342] Reihenfolge

[sgu342] Reihenfolge

题目描述

给定两个正整数 A,BA,B。你需要把 AA 表示成若干个 BB 的整数次幂的代数和,并使项数尽可能少。也就是说,要求

A=s1Bk1+s2Bk2+⋯+snBknA=s_1B^{k_1}+s_2B^{k_2}+\cdots+s_nB^{k_n},

其中每个 si∈{−1,1}s_i\in\{-1,1\},每个 kik_i 都是整数。求最小可能的项数 nn。

注意,指数 kik_i 允许为负数。

输入格式

第一行一个正整数 AA,没有前导零,十进制位数不超过 30003000。

第二行一个整数 BB,满足 1≤B≤1061\le B\le10^6。

输出格式

输出最小项数 nn。

样例

1120
10
4

数据范围

  • AA 为不超过 3000 位的正整数;
  • 1≤B≤1061\le B\le10^6。

时间限制: 0.25 秒
空间限制: 64 MB