1. 题目解析与数学原理
这道题目要求找出20万以内所有数位和能被5整除的数字。我们先拆解题目要求:
- 范围限制:1 ≤ n < 200,000
- 条件:数字n的各个数位之和是5的倍数(即sum(digits) % 5 == 0)
1.1 数位求和算法
计算一个数字的数位和是解决本题的基础操作。以数字12345为例:
c复制int digit_sum(int n) {
int sum = 0;
while(n > 0) {
sum += n % 10; // 取最后一位
n /= 10; // 去掉最后一位
}
return sum;
}
这个算法的时间复杂度是O(d),其中d是数字的位数。对于20万以内的数字,最多只有6位数(199999),所以每次计算最多进行6次循环。
1.2 数学优化思路
直接遍历1到20万检查每个数字虽然可行,但效率不高。我们可以利用数位动态规划(DP)来优化:
- 将数字视为字符串,从高位到低位处理
- 记录当前位数、数位和模5的余数、是否已经小于上限数字
- 通过记忆化减少重复计算
这种方法的复杂度可以降到O(logN),对于大范围数字更高效。不过对于20万这个数量级,直接遍历也是可以接受的。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 基础实现方案
2.1 暴力枚举法
最直观的方法是遍历1到199999,检查每个数字的数位和:
c复制#include <stdio.h>
int digit_sum(int n) {
int sum = 0;
while(n > 0) {
sum += n % 10;
n /= 10;
}
return sum;
}
int main() {
int count = 0;
for(int i = 1; i < 200000; i++) {
if(digit_sum(i) % 5 == 0) {
count++;
// 如需输出具体数字可取消下面注释
// printf("%d\n", i);
