c++ - 为什么我的函数不能用于大量数字，如何更改它？

我找到了可以解决问题的公式，但无法使它适用于大数。第n个因子为第（n-1）个因子+（n-1）*（n-1）+ n * n

所以我写了这个函数：

inline long long int formula(long long int n)
{
    if(n==1)return 1;
    return formula(n-1)+(n-1)*(n-1)+*n*n;
}

并且由于必须以666013为模来计算答案，因此我添加了这个（MOD = 666013）：

inline long long int formula(long long int n)
{
    if(n==1)return 1;
    return ((formula(n-1)%MOD+(1LL*(n-1)*(n-1))%MOD)%MOD+(1LL*n*n)%MOD)%MOD;
}

我可能没有正确使用模数。我的函数必须适用于最大为2.000.000.000的数字，并且它在大约30.000处停止工作

编辑：我已经尝试过使用循环，但我仍然无法使它适用于大于20.000.000的数字。这就是我正在使用的：

ans=1;
    for(i=2;i<=n;i++)
    {
        ans=(ans%MOD+1LL*(i-1)*(i-1)%MOD+1LL*i*i%MOD)%MOD;
    }

最佳答案

如果需要为20亿的大小进行计算，则循环将花费很长时间。但是，递归方程很容易导致

sum [i * i+(i-1)*(i-1)] = sum [2* i * i - 2*i + 1].

您可以使用the sum of first n squares的方程式和算术序列将其简化为：

2*n(n * n + 1) / 3

现在，您可以使用* b％c =（a％c）*（b％c）进一步减小此值。但是，除以3和模运算不会影响。因此，您需要将公式写为

( ((2*(n % MOD)) %MOD) * (((n % MOD) * (n % MOD)) +1) %MOD) * 444009) % MOD，

其中444009是3 mod MOD的模数倒数，即3 * 444009％MOD = 1。

编辑：添加了关于换向模和除法运算符的讨论，正如Raymond Chen指出的，模和除法不通勤。

关于c++ - 为什么我的函数不能用于大量数字，如何更改它？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33465849/