特殊数统计

版权信息：

任务总览

题目描述

小丽同学想在 1 ~ n 的范围内找到 ​这样的一类数​：

• 各个位数之和​​不能被 2 整除​，也 ​不能被 5 整除​。

例如：

• ​**3**​，各位和为 3，不能被 2 或 5 整除 ✅
• ​**12**​，各位和为 1 + 2 = 3，不能被 2 或 5 整除 ✅
• ​**25**​，各位和为 2 + 5 = 7，不能被 2 或 5 整除 ✅
• ​**30**​，各位和为 3 + 0 = 3，不能被 2 或 5 整除 ✅
• ​**100**​，各位和为 1 + 0 + 0 = 1，不能被 2 或 5 整除 ✅

请你编写程序，统计 满足条件的数 在 1 ~ n 之间的个数。

输入格式

一个整数 n，表示范围的上限（1 ≤ n ≤ 9999）。

输出格式

输出 1 ~ n​之间满足条件的数的个数​。

样例

输入

50

输出

20

提示

1. ​计算位数和​：
   • 将 num 转换为字符串 str(num)，然后求各个位数字之和。
   • 例如：sum(int(d) for d in str(num)) 计算 num 的各个位数之和。
2. ​判断整除性​：
   • 如果 位数和sum_digits 能被 ​2 或 5 整除​，则跳过。
   • 否则，计入结果。

时间复杂度分析

由于 n 最大为 9999，​最多 4 位数​，因此 O(n log n)​完全可行​。

总结

• ​遍历 1 ~ n​，计算 ​各个位数之和​。
• ​检查整除性​，如果 ​不能被 2 或 5 整除​，则计入结果。
• ​时间复杂度 O(n log n)​，适用于 n ≤ 9999 的范围。