为什么我的函数不适用于大数，我该如何更改它？

Question

我找到了一个解决问题的公式，但我不能让它适用于大数。第 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;
    }

Answer 1

我不明白你为什么要为此使用递归函数。它会在少量调用时工作，但如果你递归调用它几百万次，那么......它不会。原因是您在另一个函数内的另一个函数内调用一个函数......太多次导致程序崩溃或命名为 "Stack Overflow".

克服这个问题的最好方法是使用循环来修复它！只需从 0 迭代到 n（n 是您要获取的数字）。

Answer 2

您的代码的迭代版本在下面。你可以使用它

    inline long long int formula(long long int n)
    {
        long long f = 1;
        for (int i = 2; i <= n; i++)
        {
            f = ((f % MOD + (1LL * (i - 1)*(i - 1)) % MOD) % MOD + (1LL * i*i) % MOD) % MOD;
        }
        return f;
    }

Answer 3

尽可能简化，以便能够看到需求：

typedef long long val_t;
#define MOD         ((val_t) 666013)

// for really big numbers, change #if to 1
#if 0
#define MODOF(_x)   ((_x) % MOD)
#else
#define MODOF(_x)   (_x)
#endif

#define SQR(_i)     MODOF((_i) * (_i))

val_t
formula(val_t n)
{
    val_t i;
    val_t ans;

    ans = 0;

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

    return ans;
}

更新：我太习惯在这里看到阶乘了，以至于我写错了公式。现已更正。

Answer 4

如果要计算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

现在您可以使用 a * b % c = (a % c) * (b %c) 进一步减少它。但是，除以 3 和 modulus 运算不会交换。所以你需要把等式写成

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

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

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

为什么我的函数不适用于大数，我该如何更改它？

Why doesn't my function work for large numbers and how can I change it?

c++

modulo