1 条题解
-
0
区间倍数累加和 题解
思路概述
本题考察基础一维循环(
for循环或while循环)以及累加器的使用:- 使用
for循环枚举 内的所有整数,判断是否能被 整除:
long long sum = 0; for (int i = 1; i <= n; i++) { if (i % k == 0) { sum += i; } }或者直接以步长 循环累加:
long long sum = 0; for (int i = k; i <= n; i += k) { sum += i; }- 注意当 时,累加和为 $\frac{10^5 \times (10^5 + 1)}{2} \approx 5 \times 10^9$,会超出 32 位整型范围,因此累加变量
sum必须声明为long long。
正确性说明
循环遍历所有合法元素并进行累加,结果严格等于定义式。
复杂度分析
- 时间复杂度:使用步长循环为 ,步长为 1 遍历为 ,在 约束下均可在毫秒级运行完毕。
- 空间复杂度:。
- 使用
信息
- ID
- 120
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者