19959: 倍数求和

http://cs101.openjudge.cn/practice/19959/

输入一个数正整数n (n <= 10^12),求式子

的值。也就是求k在[1,n]内的所有倍数和。

输入

第一行为一个正整数n，n<=10^12

输出

计算式子的值

样例输入

Sample1 Input:
9

Sample1 Output:
130

解释: k=1时,x取1，2，3，4，5，6，7，8，9，合计45；k=2时，x取2，4，6，8，合计20；k=3时，x取3，6，9，合计18；k=4时，x取4，8，合计12；k=5、6、7、8、9时，x分别取5，6，7，8，9，合计35；式子的值即总和为130

样例输出

Sample2 Input:
15

Sample2 Output:
406

Sample3 Input:
1

Sample3 Output:
1

来源

cs101-2019 周畅

python

def calculate_sum(n):
    # 快速计算 1 到 n 的和
    def sum_range(x):
        return x * (x + 1) // 2

    # 主要逻辑
    result = sum_range(n)
    k = n // 2
    temp1 = 2

    while k >= 1:
        temp2 = (n // k) + 1
        # 当前范围和
        range_sum = sum_range(temp2 - 1) - sum_range(temp1 - 1)
        # 更新结果
        result += range_sum * (k * (k + 1)) // 2
        # 更新 k 和 temp1
        k = n // temp2
        temp1 = temp2

    return result

# 输入
n = int(input())
print(calculate_sum(n))

该解法高效地计算了以下数学表达式的总和： $S = \sum_{k = 1}^{n} \sum_{x是k的倍数} x$ 它利用了数学优化方法，使得时间复杂度降至 $ O(\sqrt{n}) $。
关键概念
sum_range(x) 计算 1 到 x 的和
python
def sum_range(x):
    return x * (x + 1) // 2
该函数返回从 1 到 ( x ) 的所有整数的和，利用了求和公式： $1 + 2 + \dots + x = \frac{x (x + 1)}{2}$
第一步：初始化 result
python
result = sum_range(n)
由于所有数（1 到 n ）都至少被 1 整除一次，首先将其总和加到 result 中： $S = 1 + 2 + \dots + n = \frac{n (n + 1)}{2}$
核心优化：合并计算多个 k 值的贡献
python
k = n // 2
temp1 = 2
k = n // 2 表示当前处理的 k 取值，初始设为 ( n // 2 )。
temp1 = 2 作为区间下界。
核心循环
python
while k >= 1:
    temp2 = (n // k) + 1
temp2 计算 n // k 变化的下一段边界。
关键思想是：当 ( k ) 在一定范围内时，n // k 的值是恒定的。
例如，若 n = 9：
k = 1 时：n // 1 = 9
k = 2 时：n // 2 = 4
k = 3,4 时：n // k = 3
k = 5,6,7,8,9 时：n // k = 1
这些可以被分段处理，而非单独计算每个 k。
计算当前 k 对 result 的贡献
python
range_sum = sum_range(temp2 - 1) - sum_range(temp1 - 1)
range_sum 计算区间 [temp1, temp2-1] 内的整数和，表示 k 在 [temp1, temp2-1] 内的所有 x 贡献的总和。
计算方式：用 sum_range(temp2-1) 减去 sum_range(temp1-1)，即： $\sum_{x = t e m p 1}^{t e m p 2 - 1} x = \sum_{x = 1}^{t e m p 2 - 1} x - \sum_{x = 1}^{t e m p 1 - 1} x$
更新 result
python
result += range_sum * (k * (k + 1)) // 2
range_sum 是某段 k 范围的整数之和。
(k * (k + 1)) // 2 是 k 的倍数和公式： $k \cdot (1 + 2 + \dots + ⌊ n / k ⌋) = k \times \frac{⌊ n / k ⌋ \times (⌊ n / k ⌋ + 1)}{2}$
将两者相乘，即得到 k 在该范围对最终 result 的贡献。
更新 k 和 temp1
python
k = n // temp2
temp1 = temp2
由于 temp2 是 n // k + 1，k 更新为 n // temp2，即 k 直接跳到下一个区间的最大 k。
temp1 = temp2，下次迭代时新的 temp1 代表当前区间的起点。
时间复杂度分析
由于 k 每次按 n // k 变化，k 变化的次数大约是 O(√n)（因为 n // k 主要变化在 √n 左右）。
因此，该解法的时间复杂度为 O(√n)，远优于 O(n) 的朴素解法。
示例分析
输入 n = 9
计算过程
sum_range(9) = 45，初始化 result = 45
进入循环：
k=4, temp1=2
temp2=5，计算 [2, 4] 的 range_sum = sum_range(4) - sum_range(1) = 10 - 1 = 9
贡献 9 × (4×5/2) = 9 × 10 = 90
更新 result = 45 + 90 = 135
k = 9//5 = 1, temp1 = 5
继续：
temp2 = 10
range_sum = sum_range(9) - sum_range(4) = 45 - 10 = 35
贡献 35 × (1×2/2) = 35 × 1 = 35
result = 135 + 35 = 130
终止循环。
最终输出：
130
总结
该方法利用数学优化，跳过了 O(n) 的计算，实现 O(√n) 复杂度。
通过 sum_range(x) 快速求和，避免逐个遍历 k。
通过 temp1 和 temp2 分段处理，确保 k 只计算关键区间。
适用于 n 最大到 ( 10^{12} )，高效且实用。
该解法比直接暴力求解 快很多，是一个巧妙的数学优化方法！ 🚀

python

def main():
    import sys
    input_data = sys.stdin.read().strip()
    if not input_data:
        return
    n = int(input_data)
    ans = 0
    k = 1
    # Process intervals where floor(n/k) remains constant.
    while k <= n:
        m = n // k         # For current k, m is floor(n/k)
        r = n // m         # r is the maximum k with the same floor(n/k)
        # Sum of k in the interval [k, r]
        sum_k = (k + r) * (r - k + 1) // 2
        # For each k, the sum of its multiples up to n is k * (1+2+...+floor(n/k))
        # and the inner sum equals m*(m+1)//2.
        ans += sum_k * (m * (m + 1) // 2)
        k = r + 1

    print(ans)

if __name__ == "__main__":
    main()

Explanation
Understanding the Problem:
For each integer ( k ) from 1 to ( n ), we need to sum up all multiples of ( k ) that are less than or equal to ( n ).
The multiples of ( k ) are $ k, 2k, 3k, \dots, \lfloor \frac{n}{k} \rfloor \cdot k $.
The sum for a fixed ( k ) is $ k \times \frac{\lfloor \frac{n}{k} \rfloor (\lfloor \frac{n}{k} \rfloor + 1)}{2} $.
Optimization:
Since ( n ) can be as large as ( 10^{12} ), iterating from 1 to ( n ) is not feasible.
We optimize by grouping intervals where $ \lfloor \frac{n}{k} \rfloor $ remains constant.
For a given $ m = \lfloor \frac{n}{k} \rfloor $, the value of ( k ) remains constant for ( k ) in the interval ([L, R]) where $ L = \lfloor \frac{n}{m+1} \rfloor + 1 $ and $ R = \lfloor \frac{n}{m} \rfloor $.
Algorithm:
Use a while-loop to process segments of ( k ) where $ \lfloor \frac{n}{k} \rfloor $ is constant.
Compute the sum of ( k ) over each segment using the arithmetic sum formula.
Multiply the segment sum by $ \frac{m(m+1)}{2} $ (the sum of numbers from 1 to m ).
Add to the final answer and move k to the next segment.
Input/Output:
The program reads the input number n and prints the computed result.
This solution efficiently computes the desired sum even for very large values of n .

19959: 倍数求和 ​

输入 n = 9 ​

19959: 倍数求和

输入 `n = 9`