题目链接

小乐乐求和

题目描述

计算从 1 到一个给定的正整数 n 的所有自然数之和。 即计算：1 + 2 + 3 + ... + n

输入描述: 输入一个正整数 n (1 ≤ n ≤ 1,000,000,000)。

输出描述: 输出一个整数，表示从 1 到 n 的自然数之和。

解题思路

本题要求计算一个等差数列的和。

方法一：循环（不推荐） 最直观的方法是使用一个循环，从 1 累加到 n。但题目的数据范围 n 高达 10^9，直接循环会导致程序运行时间过长，从而超时（Time Limit Exceeded）。

方法二：高斯求和公式（推荐） 这是一个著名的数学问题，其最优解是使用等差数列求和公式（也称高斯求和公式）： Sum = n * (n + 1) / 2

这个公式可以在常数时间内计算出结果，非常高效。

关键点：数据类型 由于 n 的最大值是 10^9，n * (n + 1) 的结果会大约是 10^18，这个值会超出标准 32 位整型 (int) 的最大范围（约 2 * 10^9），导致数据溢出。因此，在计算和存储结果时，必须使用 64 位整型（C++中的 long long，Java中的 long）来避免错误。

代码

#include <iostream>

using namespace std;

int main() {
    // 使用 long long 来防止 n * (n + 1) 的计算结果溢出
    long long n;
    cin >> n;
    
    // 应用高斯求和公式
    long long sum = n * (n + 1) / 2;
    
    cout << sum << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 使用 long 来防止 n * (n + 1) 的计算结果溢出
        long n = sc.nextLong();
        
        // 应用高斯求和公式
        long sum = n * (n + 1) / 2;
        
        System.out.println(sum);
    }
}

# Python 的 int 类型可以自动处理大整数，无需担心溢出
n = int(input())

# 应用高斯求和公式
# 使用 // 保证整数除法
sum_val = n * (n + 1) // 2

print(sum_val)

算法及复杂度

  • 算法：高斯求和公式。
  • 时间复杂度： - 这是一个直接的数学计算，与 n 的大小无关。
  • 空间复杂度： - 仅需常数空间存储变量。