← 返回题目列表

AtCoder · ndpc2026_p

P. 最长递增子序列

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

分数: 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 。