← 返回题目列表

AtCoder · pakencamp_2021_day3_c

C. 数字总和

中文机器翻译题面 查看原题

配点 : 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
  • 所有输入均为整数

小課題

  1. (100 点) 1 \le L \le R \le 10^6
  2. (150 点) M=3
  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__