分数: 7 点
问题陈述
对于正整数 n,定义 f(n) 如下:
- 让 n 有 d 十进制表示的数字。定义一个序列 A = (A_1, \dots, A_d) 长度 d 如下:
- A_i 是 i- 十进制表示中从左边算起的第一个数字 n.
- 让 f(n) 是最长严格递增子序列的长度 A.
例如, f(347) = 3, f(1192) = 2, f(10123456789) = 10,和 f(11111) = 1.
给你一个正整数 N.
统计正整数的个数 x 这样通过重复应用操作 x \to x + f(x) 零次或多次,即可获得 N.
你被给予 T 测试用例。解决它们中的每一个。
约束
- 1 \leq T \leq 2 \times 10^4
- 1 \leq N \leq 10^{18}
- 所有输入值均为整数
输入
输入由标准输入给出,格式如下:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
N
输出
打印 您选择的 T 行。 i第行,输出答案 i- 第一个测试用例。
示例输入 1
6 7 110 1000000000000000000 567784738694904180 555056967895592095 942135357890920474
示例输出 1
7 5 1000000000000000000 23644 22551 60795
例如,在第二个测试用例中,从 x = 102 并重复应用该操作 x \to x + f(x):
- 102 \to 104 \to 106 \to 108 \to 110
我们可以得到 N = 110.唯一的值 x 满足条件的是 x = 102, 104, 106, 108, 110,所以有 总共 5 。