该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

AT_abc336_e [ABC336E] Digit Sum Divisible

题目描述

我们将正整数 $n$ 的各位数字之和定义为将 $n$ 用十进制表示时各位数字的和。例如，$2024$ 的各位数字之和为 $2+0+2+4=8$。
当正整数 $n$ 能被其各位数字之和整除时，我们称 $n$ 为好整数。例如，$2024$ 能被其各位数字之和 $8$ 整除，因此是好整数。
给定一个正整数 $N$，请你计算不超过 $N$ 的好整数有多少个。

输入格式

输入包含一行，格式如下：

$N$

输出格式

输出不超过 $N$ 的好整数的个数。

样例 1

输入

20

输出

13

样例 2

输入

2024

输出

409

样例 3

输入

9876543210

输出

547452239

说明/提示

限制

• $1 \leq N \leq 10^{14}$
• $N$ 是整数

样例解释 1

不超过 $20$ 的好整数有 $1,2,3,4,5,6,7,8,9,10,12,18,20$ 共 $13$ 个。

由 ChatGPT 4.1 翻译