配点 : 500 点
故事
在帕肯王国,对于某个正整数, ID 如下 M 定义为数字之和。顺便说一下,乌龟5555,帕肯王国的居民, 5 我喜欢力量。因此,连续几次 5 我决定找到他们权力的 ID 总和。 对于
問題文
正整数 n,k 反对 f_k(n) , n 可以得到第 10 基本系统下方 k 定义为数字之和。例如, 给出了 f_2(314)=5,f_1(100)=0,f_{100}(1)=1 。
正整数 L,R,M ,所以 \displaystyle \sum_{k=L}^R f_M(5^k) 。
制約
- 1 \le L \le R \le 10^{16}
- 1 \le M \le 16
- 所有输入均为整数
小課題
- (100 点) 1 \le L \le R \le 10^6
- (150 点) M=3
- (250 点)没有额外的限制。
入力
输入是按以下格式从标准输入给出的。
L R M
出力
打印答案。 来自
入力例 1
2 4 3
出力例 1
28
f_3(25)=7, f_3(125)=8, f_3(625)=13 捻 28 。
此输入/输出满足所有子任务约束。
入力例 2
333 4444 5
出力例 2
77100
这个输入/输出是一个小任务 满足 1,3 约束。
入力例 3
12 998244353 5
出力例 3
18717081408
此输入是一个小作业 3 约束。
入力例 4
12321 123456787654321 16
出力例 4
8395076630065056
此输入是一个小作业 3 约束。
原案: 海龟0123__