Toggle navigation
编绘童年
F.A.Qs
ProblemSet
Source/Category
Status
Ranklist
Contest
Login
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
达人赛白银组