整数溢出还是编码低效？1到n求和公式法异常问题咨询

问题真实原因 #

你猜的没错，就是整数溢出导致的：

• 代码里n是int类型，通常int的最大值是2^31-1（即2147483647）。当输入n=1000000时，n*(n+1)的结果是1000000*1000001=1000001000000，这个数值远大于int的最大值。
• 两个int类型相乘的结果依然是int，溢出后会触发有符号整数的未定义行为（常见表现是补码循环，结果变成负数）。之后再把这个溢出后的负数赋值给long long，自然得不到正确结果。
• 最终结果500000500000远小于long long的最大值（约9e18），所以long long完全能存下最终结果，问题出在乘法步骤的类型不匹配。

修复方法 #

不需要用更大的变量类型，只需要保证乘法运算时的类型是long long即可，有两种简单方案：

方案1：强制转换其中一个操作数为long long #

在乘法前把n转成long long，这样整个乘法运算会以long long类型执行，避免溢出：

#include <bits/stdc++.h>
using namespace std;

int main () {
    int n;
    cin >> n;
    long long sum = (long long)n * (n + 1) / 2;
    cout << sum << endl;
    return 0;
}

方案2：直接将n声明为long long类型 #

如果输入的n可能接近int的最大值，直接把n定义为long long更稳妥，这样所有运算都会以long long进行：

#include <bits/stdc++.h>
using namespace std;

int main () {
    long long n;
    cin >> n;
    long long sum = n * (n + 1) / 2;
    cout << sum << endl;
    return 0;
}

另外补充：公式法本身是**O(1)**时间复杂度，比循环的O(n)高效得多，不存在写法低效的问题，只是你之前的代码没处理好类型转换导致溢出。

内容的提问来源于stack exchange，提问作者Ksr