算法题（模数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的值取决于某些标准：

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

10 ^ 9 + 7满足两个条件。它是第一个10位数的质数, 也适合int数据类型。实际上, 任何小于2 ^ 30的素数都可以, 以防止可能的溢出。
模数的使用方式：
模的一些分布特性如下：

(a + b)％c =((a％c)+(b％c))％c
(a * b)％c =((a％c)*(b％c))％c
(a – b)％c =((a％c)–(b％c))％c
(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 = 798848767Method 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)

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的结果, 则不应执行