题解 | #下取整乘积求和#

题目链接

PEEK65 下取整乘积求和

题目描述

对于给定的正整数 $N$ ，求表达式 $\sum_{i=1}^{N} i \cdot \lfloor \frac{N}{i} \rfloor$ 的值。

解题思路

本题是 整除分块（也称 数论分块）算法的又一个典型应用。

由于 $N$ 的范围可以达到 $10^9$ ，使用 $O(N)$ 的朴素循环来计算每一项的和是不可行的，会导致超时。

核心观察与分块计算

我们注意到，在表达式 $\lfloor \frac{N}{i} \rfloor$ 中，存在许多连续的 $i$ 会得到完全相同的商。我们可以将这些 $i$ 划分成块，并对每个块进行整体计算。

假设对于一个块，其范围是 [l, r]，在这个区间内所有的 $i$ 都有相同的商 $v = \lfloor \frac{N}{i} \rfloor$ 。那么这个块对总和的贡献为：

$\sum_{i=l}^{r} i \cdot \lfloor \frac{N}{i} \rfloor = \sum_{i=l}^{r} i \cdot v = v \cdot \sum_{i=l}^{r} i$

其中 $\sum_{i=l}^{r} i$ 是一个等差数列，其和为 $\frac{(l+r) \cdot (r-l+1)}{2}$ 。

块的边界与算法流程

算法的关键在于，对于一个块的左边界 $l$ ，我们可以通过公式 $r = \lfloor \frac{N}{\lfloor \frac{N}{l} \rfloor} \rfloor$ 快速计算出它的右边界 $r$ 。算法流程如下：

初始化答案 ans = 0，左边界 l = 1。
当 l <= N 时，循环：

a. 计算当前块的商 v = N / l 和右边界 r = N / v。

b. 计算等差数列的和 sum_i = (l + r) * (r - l + 1) / 2。

c. 将贡献 v * sum_i 累加到 ans 中。

d. 更新 l = r + 1，进入下一个块。

该算法的时间复杂度为 $O(\sqrt{N})$ 。

关于数据溢出

当 $N$ 达到 $10^9$ 时，最终答案和中间计算结果（如 v * sum_i）可能会超过标准的64位整数（C++ 中的 long long）的表示范围（约 $9 \cdot 10^{18}$ ）。因此，需要使用能够处理更大数值的整数类型，例如 C++ 中的 __int128_t、Java 中的 BigInteger，或者利用 Python 对大整数的内置支持。

代码

c++
java
python

#include <iostream>

using namespace std;

// 用于输出 __int128_t 类型的函数
void print_128(__int128_t n) {
    if (n == 0) {
        cout << 0;
        return;
    }
    string s = "";
    while (n > 0) {
        s += (n % 10) + '0';
        n /= 10;
    }
    for (int i = s.length() - 1; i >= 0; --i) {
        cout << s[i];
    }
}

int main() {
    long long n;
    cin >> n;

    __int128_t ans = 0;
    for (long long l = 1, r; l <= n; l = r + 1) {
        long long v = n / l;
        r = n / v;
        __int128_t sum_l = l;
        __int128_t sum_r = r;
        // 计算 (l+r)*(r-l+1)/2
        __int128_t sum_i = (sum_l + sum_r) * (sum_r - sum_l + 1) / 2;
        ans += v * sum_i;
    }

    print_128(ans);
    cout << "\n";

    return 0;
}

import java.util.Scanner;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();

        BigInteger ans = BigInteger.ZERO;
        BigInteger two = BigInteger.valueOf(2);

        for (long l = 1, r; l <= n; l = r + 1) {
            long v = n / l;
            r = n / v;

            BigInteger bigL = BigInteger.valueOf(l);
            BigInteger bigR = BigInteger.valueOf(r);
            BigInteger bigV = BigInteger.valueOf(v);

            // (l+r) * (r-l+1) / 2
            BigInteger sumI = bigL.add(bigR)
                               .multiply(bigR.subtract(bigL).add(BigInteger.ONE))
                               .divide(two);
            
            ans = ans.add(bigV.multiply(sumI));
        }

        System.out.println(ans);
    }
}

def solve():
    n = int(input())
    
    ans = 0
    l = 1
    while l <= n:
        v = n // l
        r = n // v
        
        # 等差数列求和 (l+r)*(r-l+1)//2
        sum_i = (l + r) * (r - l + 1) // 2
        ans += v * sum_i
        
        l = r + 1
        
    print(ans)

solve()

算法及复杂度

算法：整除分块 (Integer Division Block)
时间复杂度： $O(\sqrt{N})$ 。
空间复杂度： $O(1)$ 。