1 条题解

  • 0
    @ 2026-11-7 21:58:57

    区间倍数累加和 题解

    思路概述

    本题考察基础一维循环(for 循环或 while 循环)以及累加器的使用:

    1. 使用 for 循环枚举 [1,n][1, n] 内的所有整数,判断是否能被 kk 整除:
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        if (i % k == 0) {
            sum += i;
        }
    }
    

    或者直接以步长 kk 循环累加:

    long long sum = 0;
    for (int i = k; i <= n; i += k) {
        sum += i;
    }
    
    1. 注意当 n=105,k=1n = 10^5, k = 1 时,累加和为 $\frac{10^5 \times (10^5 + 1)}{2} \approx 5 \times 10^9$,会超出 32 位整型范围,因此累加变量 sum 必须声明为 long long。

    正确性说明

    循环遍历所有合法元素并进行累加,结果严格等于定义式。

    复杂度分析

    • 时间复杂度:使用步长循环为 O(n/k)O(n/k),步长为 1 遍历为 O(n)O(n),在 n≤105n \le 10^5 约束下均可在毫秒级运行完毕。
    • 空间复杂度:O(1)O(1)。
    • 1

    信息

    ID
    120
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    递交数
    1
    已通过
    1
    上传者