题意

计算闭区间 $[m,n]$ 中所有能被 17 整除的数的和。

思路

不小于 left 的首个 17 倍数是 (left + 16) // 17 * 17。之后每次加 17，range 不会生成不满足整除条件的数；若首项超过右端点，空 range 的和自然为 0。

代码

Python代码

1
2
3left, right = map(int, input().split())
first_multiple = (left + 16) // 17 * 17
print(sum(range(first_multiple, right + 1, 17)))

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13#include <cstdio>

int main(){
    int m,n;
    scanf("%d%d",&m,&n);
    int i,sum = 0;
    for(i=m;i<=n;i++){
        if( i % 17 == 0)
            sum += i;
    }
    printf("%d\n",sum);
    return 0;
}

复杂度

设区间内 17 的倍数个数为 $k$，时间复杂度为 $O(k)$，额外空间复杂度为 $O(1)$。

总结

整除筛选可以先定位第一个倍数，再按除数步进，减少无效检查。