Tarzan的优美区间

Tarzan的优美区间

Problem Description

Tarzan 现在想要知道,区间 [L,R] 内有多少数是优美的。我们定义一个数是优美的,这
个数字要满足在它 C 进制下的各位数字之和可以整除这个数字本身。 Tarzan 不会做这道题,
他希望你能帮他求出这个问题的答案。

Input format

第一行三个十进制正整数 L,R,C, L 和 R 给的是十进制形式

Output format

一行一个整数表示被认为优美的数的数量。

Examples

input 1

5 15 10

output 1

7

input 2

2 100 2

output 2

29

Constrains and Notes

对于 30% 的数据满足: R − L ≤ 100000
对于另外 10% 的数据满足: C = 2
对于另外 20% 的数据满足: C = 10
对于 100% 的数据满足: 1 ≤ L ≤ R ≤ 1018; 2 ≤ C ≤ 15
时间限制:3s,空间限制:256MB
(因为评测机性能特别咕咕咕,最后两个点限时3.5s)

信息

ID
1395
难度
9
分类
动态规划 点击显示
标签
(无)
递交数
1
已通过
1
通过率
100%
被复制
1
上传者