/ 
実行時間制限: 10 sec / メモリ制限: 1024 MB
配点 : 525 点
問題文
正整数 n の 桁和 を、n を 10 進法で表したときの各桁の和として定義します。例えば 2024 の桁和は 2+0+2+4=8 です。
正整数 n が n の桁和で割り切れる時、n を 良い整数 と呼びます。例えば 2024 はその桁和である 8 で割り切れるので良い整数です。
正整数 N が与えられます。N 以下の良い整数は全部で何個ありますか？
制約
- 1 \leq N \leq 10^{14}
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N 以下の良い整数の個数を出力せよ。
入力例 1
20
出力例 1
13
20 以下の良い整数は 1,2,3,4,5,6,7,8,9,10,12,18,20 の 13 個です。
入力例 2
2024
出力例 2
409
入力例 3
9876543210
出力例 3
547452239
Score: 525 points
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