Problem2097--编绘童年数

2097: 编绘童年数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 107  Solved: 31
[Status] [Submit] [Creator:]

Description

童年兔有一天在思考这样一个问题:“这个世界上有很多特殊的数,比如:回文数、质数、水仙花数,……。那么我是否可以创造一个具有特殊性质的数呢?”

于是她创造了“编绘童年数”,编绘童年数是这么定义的:

对于一个 m 位整数 a 来说,它的最高位是第1位,如果 a 的第 1 位对应的数字能被 1 整除,前 2 位对应的数字能被 2 整除,前 3 位对应的数字能被 3 整除,……,前 m 位对应的数字能被 m 整除,则称其为 “编绘童年数”。
如261这个数字,第1位是2能被1整除,前两位26能被2整除,前三位261能被3整除,它就是一个“编绘童年数”

请计算在 1 到 n 范围内(包括 1 和 n)的所有整数中,有多少数是编绘童年数。

Input

一个整数 n(1 ≤ n ≤ 1,000,000,000)。

Output

一个整数,表示 1 到 n 范围内编绘童年数的个数。

Sample Input Copy

50

Sample Output Copy

30

HINT

样例解释:
1 到 50 范围内的“编绘童年数”有:1,2,3,4,5,6,7,8,9,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50。

数据规模与约定:
对于 30% 的数据,n ≤ 1,000
对于 60% 的数据,n ≤ 1,000,000
对于 100% 的数据,1 ≤ n ≤ 1,000,000,000

Source/Category