算法题：模数10 ^ 9 + 7（1000000007）

本文概述

• C ++
• Python3
• C ++
• Python3
• C ++
• Java
• Python3
• C#

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

什么是模运算：

在两个操作数上进行除法运算后获得的余数称为模运算。进行模运算的运算符是‘％’。例如：a％b = c, 这意味着, 当a除以b时, 将得到余数c, 7％2 = 1、17％3 = 2。

为什么我们需要取模：

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

由于这些原因，习题者需要给出某个数N的模的结果。

N的值取决于某些标准：

1. 它应该足够大以适合最大的整数数据类型, 即确保没有结果溢出。
2. 它应该是质数, 因为如果我们将质数取为质数, 则结果通常是隔开的, 即与非质数的质数相比, 结果是非常不同的结果, 这就是质数通常用于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

所以，modulo是对+，*和-的分布，但不是对/[请参阅模除法的细节]

注意：(a％b)的结果将始终小于b。

对于计算机程序, 由于变量限制的大小, 我们在每个中间阶段执行模M 这样就不会发生范围溢出。

Example:
a = 145785635595363569532135132
b = 3151635135413512165131321321
c = 999874455222222200651351351
m = 1000000007
Print (a*b*c)%m.

Method 1:
First, multiply all the number and then take modulo:
(a*b*c)%m = (459405448184212290893339835148809
515332440033400818566717735644307024625348601572) % 
1000000007
a*b*c does not fit even in the unsigned long long 
int due to which system drop some of its most 
significant digits. Therefore, it gives the wrong answer.
(a*b*c)%m = 798848767

Method 2:
Take modulo at each intermediate steps:
i = 1
i = (i*a) % m    //i = 508086243
i = (i*b) % m    //i = 144702857
i = (i*c) % m    //i = 798848767
i = 798848767 

Method 2 always gives the correct answer.

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

C ++

unsigned long long factorial( int n)
{
     const unsigned int M = 1000000007;
     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 = 1000000007
     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 = 1000000007;
 
     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 = 1000000007
     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到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;
}
 
//This code is contributed by
//Shubham Singh(SHUBHAMSINGH10)

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

模乘逆(MMI)：

数y的乘法逆是z

iff(z * y)== 1。

将数字x除以另一个数字y等于将x乘以y的逆。

x/y == x * y ^(-1)== x * z(其中z是y的乘法逆)。

在常规算术中, y的乘法逆是浮点值。例如：7的乘法逆是0.142…, 3的乘法逆是0.333…。

在数学中, 整数" a"的模乘乘法逆是整数" x", 因此乘积ax相对于模数m等于1。

ax= 1(mod m)

将ax除以整数m后的余数为1。

Example:
If M = 7, the MMI of 4 is 2 as (4 * 2) %7 == 1, If M = 11, the MMI of 7 is 8 as (7 * 8) % 11 == 1, If M = 13, the MMI of 7 is 2 as (7 * 2) % 13 == 1.

观察到一个数字的MMI对于不同的M可能会有所不同。

因此, 如果我们在程序中执行模算术, 并且需要运算x/y的结果, 则不应执行

z = (x/y) % M;

相反, 我们应该执行

y_inv = findMMI(y, M);
z = (x * y_inv) % M;