Score: $525$ points

问题描述

在正整数 $n$ 中，其数字和被定义为 $n$ 的十进制表示中所有数字的和。例如，数字 $2024$ 的数字和为 $2+0+2+4=8$。

一个正整数 $n$ 被称为良数，当且仅当 $n$ 可以被它的数字和整除。例如，$2024$ 是一个良数，因为它可以被其数字和 $8$ 整除。

现在给定一个正整数 $N$，请计算不大于 $N$ 的良数有多少个？

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

The digit sum of a positive integer $n$ is defined as the sum of the digits in the decimal notation of $n$. For example, the digit sum of $2024$ is $2+0+2+4=8$.
A positive integer $n$ is called a good integer when $n$ is divisible by its digit sum. For example, $2024$ is a good integer because it is divisible by its digit sum of $8$.
You are given a positive integer $N$. How many good integers are less than or equal to $N$?

Constraints

• $1 \leq N \leq 10^{14}$
• $N$ is an integer.

Input

The input is given from Standard Input in the following format:

$N$

Output

Print the number of good integers less than or equal to $N$.

Sample Input 1

20

Sample Output 1

13

There are $13$ good integers less than or equal to $20$: $1,2,3,4,5,6,7,8,9,10,12,18,20$.

Sample Input 2

2024

Sample Output 2

409

Sample Input 3

9876543210

Sample Output 3

547452239

update @ 2024/3/10 01:25:34