如何使用模 10^9+7

Question

我正在尝试编写自然数平方和的代码，但使用 mod 它给出了错误的答案。这里正确的方法是什么？

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

int main()
{
    int N;
    cin>>N;
    cout<< (((N) * (N+1) * (2*N+1))/6)%mod;

    return 0;
}

Answer 1

(N) * (N+1) * (2*N+1)即使N小于 1000000007，也可能太大。即最多2000000039000000253000000546，这是一个91位的数字。您的系统不太可能int包含如此大的数字。

与此类问题一样，解决方法是以下组合：

• 对中间产品使用更大的整数类型，以及
• 对中间产品应用模归约，而不仅仅是在最后。

仅使用其中之一是不够的。

由于较早应用模归约，除以 6 无法与普通除法一起使用，它必须是 6 mod 1000000007 的模乘逆的乘法，即 166666668。

示例代码：

mod_mul(mod_mul(mod_mul(N, N + 1, mod), mod_mul(2, N, mod) + 1, mod), inv6, mod)

使用 的一些合适的定义mod_mul，可以通过使用long long或类似的类型来避免溢出。