翻译：算法常见的模数1000000007 模数10 ^ 9 + 7

大家好，我是讯享网，很高兴认识大家。

说明

在大多数编程比赛中，我们都需要以10 ^ 9 + 7模为模来回答结果。这背后的原因是，如果问题约束是大整数，则只有高效的算法才能在允许的有限时间内解决它们。

//int MOD = 1000_000_007; final int MOD = (int)1e9 + 7;

讯享网

什么是模运算：

采用Mod的原因是为了防止整数溢出。C / C ++中最大的整数数据类型是64位无符号long long int，可以处理从0到（2 ^ 64 – 1）的整数。但是，在某些产出增长率很高的问题中，这种高范围的无符号长久可能不够。
假设在64位变量’A’中存储2 ^ 62，在另一个64位变量’B’中存储2 ^ 63。当我们将A和B相乘时，系统不会给出运行时错误或异常。它只是进行一些伪计算并存储伪结果，因为结果的位大小是在乘法溢出后得出的。
在某些问题中，需要计算结果取模逆，并且该数很有用，因为它是质数。同样，这个数字应该足够大，否则在某些情况下模块化逆技术可能会失败。

它应该足够大以适合最大的整数数据类型，即确保没有结果溢出。
它应该是质数，因为如果我们用质数来取数的mod，则结果通常是隔开的，即与非质数的mod数相比，结果是非常不同的结果，这就是为什么质数通常用于mod。

10 ^ 9 + 7满足两个条件。它是第一个10位数的质数，也适合int数据类型。实际上，任何小于2 ^ 30的素数都可以，以防止可能的溢出。

模数的使用方式：模数

的一些分布特性如下：
1.（a + b）％c =（（a％c）+（b％c））％c
2. （a * b）％c =（（a％c）*（b％c））％c
3.（a – b）％c =（（a％c）–（b％c））％c
4.~~（a / b）％c =（（a％c）/（b％c））％c~~
因此，模是分布在+，*和–上，而不是分布在/上。[有关详细信息，请参阅模数除法]
注意：（a％b）的结果将始终小于b。
在计算机程序的情况下，由于变量限制的大小，我们在每个中间阶段执行模M，这样就不会发生范围溢出。

示例：
a = 35132
b =
c = 51351
m =
打印（a * b * c）％m。方法1：
首先，将所有数字相乘然后取模：
（a * b * c）％m =（809
0572）％

a * b * c即使在无符号long long
int中也不适合，这是由于系统下降它的一些最
重要的数字。因此，它给出了错误的答案。
（a * b * c）％m = 方法2：
在每个中间步骤取模：
i = 1
i =（i * a）％m // i =
i =（i * b）％m // i =
i =（i * c）％m // i =
i =

方法2始终给出正确的答案。

使用模但在不同位置查找大量阶乘的函数。

语言举例

C ++

讯享网unsigned long long factorial(int n) { 
    const unsigned int M = ; unsigned long long f = 1; for (int i = 1; i <= n; i++) f = f * i; // WRONG APPROACH as // f may exceed (2^64 - 1) return f % M; }

Python3

讯享网

def factorial( n) : M =  f = 1 for i in range(1, n + 1): f = f * i # WRONG APPROACH as  # f may exceed (2^64 - 1)  return f % M # This code is contributed by Shubham Singh(SHUBHAMSINGH10)

C ++

讯享网unsigned long long factorial(int n) { 
    const unsigned int M = ; unsigned long long f = 1; for (int i = 1; i <= n; i++) f = (f*i) % M; // Now f never can // exceed 10^9+7 return f; }

Python3

def factorial( n) : M =  f = 1 for i in range(1, n + 1): f = (f * i) % M # Now f never can # exceed 10^9+7  return f # This code is contributed by Shubham Singh(SHUBHAMSINGH10)

可以遵循相同的步骤进行添加。
（a + b + c）％M与（（（（a + b）％M）+ c）
％M相同。每次加一个数字时都要执行％M，以避免溢出。

注意：在大多数编程语言中（例如C / C ++），当您使用负数执行模块化运算时，会给出负结果，例如-5％3 = -2，但是模块化运算后的结果应在范围内0到n-1表示-5％3 =1。因此将其转换为正模等效值。

C ++

讯享网int mod(int a, int m) { 
    return (a%m + m) % m; }

Java

static int mod(int a, int m) { 
    return (a%m + m) % m; } // This code is contributed by  //Shubham Singh(SHUBHAMSINGH10)

Python3

讯享网def mod(a, m): return (a%m + m) % m # This code is contributed by # Shubham Singh(SHUBHAMSINGH10)

C＃

static int mod(int a, int m) { 
    return (a % m + m) % m; }

但是划分的规则不同。要在模算术中执行除法，我们首先需要了解模乘逆的概念。

参考

https://www.geeksforgeeks.org/modulo-1097-/

翻译：算法常见的模数1000000007 模数10 ^ 9 + 7

说明

什么是模运算：

模数的使用方式：模数

语言举例

参考

相关推荐