Java求和公式实现问题：Solution2输入100000时输出错误原因咨询

给定数字N，计算以下求和公式的值：
[
\sum_{X=1}^{N} {(X + 1)^2 - (3X + 1) + X}
]
输入格式：第一行输入整数n；输出格式：输出计算结果。
约束条件：1 ≤ n ≤ 10^5

现有两个Java解法，Solution1可正常运行，但Solution2在输入n=100000时输出错误：

• 正确输出：333338333350000
• 实际输出：18104913692784

Solution1（正常运行）： #

import java.util.*;
import static java.lang.Math.ceil;

class Solution {
    public long SigmaEquation(int n ) {
        long ans=0;
        for(int i=1; i<=n; i++){
            ans = ans + (long)(Math.pow((i+1),2)-((3*i)+1)+i);
        }
        return ans;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Solution Obj = new Solution();
        System.out.println(Obj.SigmaEquation(n));

    }
}

Solution2（输入100000时出错）： #

import java.util.*;
import static java.lang.Math.ceil;

class Solution {
    public long SigmaEquation(int n ) {
        long ans=0;
        for(int i=1; i<=n; i++){
            ans = ans + (((i+1)*(i+1))-((3*i)+1)+i);
        }
        return ans;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Solution Obj = new Solution();
        System.out.println(Obj.SigmaEquation(n));

    }
}

1. Solution2出现该错误的原因是什么？
2. 为何Solution1没有出现相同问题？

1. Solution2出错的原因 #

Solution2中i是int类型，Java里int的最大值是2^{31-1=2147483647。当i接近10}5时，(i+1)*(i+1)的计算结果会远超这个最大值——比如i=100000时，(100000+1)^2=10000200001，远大于int的上限，这会触发整数溢出。溢出后的数值会变成错误的正数或负数，后续的减法、加法操作都是基于这个错误值进行的，最终累加得到的结果自然不正确。

而且整个表达式(((i+1)*(i+1))-((3*i)+1)+i)的计算过程都是以int类型执行的，哪怕最后加到long类型的ans里，中间结果已经因为溢出损坏，无法修正。

2. Solution1未出现问题的原因 #

Solution1使用了Math.pow((i+1),2)，这个方法返回double类型。double的取值范围远大于int，完全能容纳(100000+1)^2这样的数值，不会出现溢出。之后通过(long)强制转换为长整型再累加，整个过程中中间结果没有被损坏，所以能得到正确值。

另外，虽然Math.pow是浮点数运算，但100001^{2=10000200001远小于double能精确表示的整数上限（2}53，约9e15），所以不会出现精度损失，结果准确。

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