优化统计指定范围内可被3或5整除数字的程序性能

原代码的核心问题 #

• 时间复杂度过高：两个版本均采用遍历区间内每个数的实现（O(n)复杂度），当区间范围极大（如b-a达到1e18量级）时，程序无法在合理时间内完成计算。
• 第二个版本属于反优化：用计算各位数字之和判断是否被3整除，比直接取模i%3==0的运算效率低很多，进一步拖慢了性能。
• 输入输出格式错误：使用%d格式符读写unsigned long long类型变量，会导致数据截断或读取异常，正确格式符应为%llu。

优化方案：数学公式直接计算 #

无需遍历每个数，利用数学规律可直接统计结果：

1. 1到n中，能被3整除的数的数量为 n // 3
2. 1到n中，能被5整除的数的数量为 n // 5
3. 1到n中，能同时被3和5整除（即被15整除）的数的数量为 n // 15——这部分数在前两次统计中被重复计算，需减去一次。

因此，1到n中满足条件的数的总数为：count(n) = n/3 + n/5 - n/15

区间[a, b]内的目标数量可通过 count(b) - count(a-1) 得到。

优化后的代码 #

#include <cstdio>

using namespace std;

unsigned long long count_valid(unsigned long long n) {
    return n / 3 + n / 5 - n / 15;
}

int main() {
    unsigned long long a, b;
    scanf("%llu%llu", &a, &b);
    unsigned long long result = count_valid(b) - count_valid(a - 1);
    printf("%llu", result);
    return 0;
}

说明 #

• 该解法时间复杂度为O(1)，无论区间范围多大，都能瞬间完成计算。
• 修正了输入输出格式错误，确保数据读写准确。
• 精准统计了“可被3或5整除”的数，避免了重复计数同时被3和5整除的情况。

内容的提问来源于stack exchange，提问作者Kanol77