Logo Infinity Online Judge

InfOJ

时间限制:1 s 空间限制:512 MB

#233. 心跳

Statistics

题目描述

对正整数 $x$,设 $f(x,B)$ 表示 $x$ 在 $B$ 进制下的数位和。说一个正整数 $p$ 是 $B$-好的,当且仅当对于任意正整数 $q\lt p$ 都有 $f(p,B)\ge f(q,B)$。

给定正整数 $n$ 和 $B$,计算有多少个 $\le n$ 的正整数是 $B$-好的。

输入格式

本题单个测试点内有多组数据。

第一行是数据组数 $T$。

接下来 $T$ 行,每行两个正整数 $n,B$。

输出格式

输出 $T$ 行,每行一个非负整数,为答案。

样例 #1

样例输入 #1

6
4 2
9 3
1000 2
1000 20
28238934 154154154154154
23389348458425 5

样例输出 #1

3
6
49
60
28238934
760

提示

样例解释

这里只解释第二组询问的输出。三进制下,$1,2,3,4,5,6,7,8,9$ 的数位和分别为 $1,2,1,2,3,2,3,4,1$,据此容易看出只有 $1,2,4,5,7,8$ 是 $3$-好的,所以输出 $6$。

数据范围

所有数据均满足:$1\le T\le 10^5$,$1\le n\le 10^{18}$,$2\le B\le 10^{18}$。

  • 子任务 $1$($50$ 分):$T\le 10^4$,$n,B\le 100$。
  • 子任务 $2$($30$ 分):$B=2$。
  • 子任务 $3$($20$ 分):无特殊限制。