UOJ Logo Universal Online Judge

UOJ

#140. 【UER #4】被粉碎的数字

统计

很久很久以前,有一个数字加入了 UOJ 群。

这天,在它讨论“一个数字应该怎么取模”的时候一不小心被删除了,变成了被粉碎的数字。

突然间,它突然发现它忘记了自己是谁。这让它感觉很焦躁,于是它来拜托你来帮它找到它所代表的整数 $x$。

在经过一番询问之后,你整理了一下现在你得到的线索:

  1. 已知整数 $R$,有 $1 \leq x \leq R$
  2. 定义函数 $f(x)$ 为 $x$ 的各位数字之和,例如 $f(13)=4,f(233)=8$。已知整数 $k$,有 $f(x)=f(k \times x)$

然而遗憾的是,你发现即使拥有了这些条件,可能的 $x$ 依然有很多个。因此,为了进一步缩小排查范围,你想要知道满足这两个条件的整数有多少个。

输入格式

仅一行两个正整数 $R$ 和 $k$。

输出格式

仅一个整数,表示可能的整数 $x$ 有多少个。

C/C++ 输入输出 long long 时请用 %lld。C++ 可以直接使用 cin/cout 输入输出。

样例一

input

100 1

output

100

explanation

因为对于所有的正整数 $x$ 都有 $f(x)=f(x)$,所以答案就是 $R$,即100。

样例二

input

10 3

output

1

explanation

只有⑨是满足条件的。

样例三

input

666666666 233

output

15272224

限制与约定

测试点编号 $R$的规模 $k$的规模
1$R \leq 10^6$$k < 1000$
2
3$R \leq 10^8$
4
5
6$R \leq 10^{18}$$k < 10$
7
8$k < 1000$
9
10

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载