模块 10^9+7 (1000000007)
在大多数程序设计竞赛中，我们被要求用 10^9+7 模回答结果。这背后的原因是，如果问题约束是大整数，只有高效的算法才能在允许的有限时间内解决它们。 什么是模运算: 对两个操作数进行除法运算后得到的余数称为模运算。做模数运算的操作员是 '%' 。举例来说:a % b = c，这意味着，当 a 除以 b，得到余数 c，7%2 = 1，17%3 = 2。 我们为什么需要取模:
-
取 Mod 的原因是为了防止整数溢出。C/C++中最大的整数数据类型是无符号长整型，它是 64 位的，可以处理从 0 到(2^64–1)的整数。但是在一些产出增长率非常高的问题中，这种高范围的无符号长多头可能是不够的。 假设在一个 64 位变量‘a’中存储了 2^62，在另一个 64 位变量‘b’中存储了 2^63。当我们将 A 和 B 相乘时，系统不会给出运行时错误或异常。它只是做一些伪计算并存储伪结果，因为结果的位大小来自乘法溢出之后。
-
在一些问题中，需要计算模逆的结果，这个数字帮助很大，因为它是质数。此外，这个数字应该足够大，否则在某些情况下，模逆技术可能会失败。
由于这些原因，问题设置者要求给出某个数的模 N 的结果。 氮的值取决于某些标准:
- 它应该足够大以适合最大的整数数据类型，即它确保结果中没有溢出。
- 它应该是一个质数，因为如果我们用质数对一个数进行模运算，结果通常是有间隔的，即与用非质数对该数进行模运算相比，结果是非常不同的，这就是为什么质数通常用于模运算的原因。
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~~
所以，模是分布在+、和–但不超过/[详情请参考模除] 注:的结果(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;
}
Java 语言(一种计算机语言，尤用于创建网站)
static long factorial(int n)
{
const long M = 1000000007;
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;
}
// This code is contributed by rutvik_56.
Python 3
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
static long factorial(int n)
{
const long M = 1000000007;
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;
}
// This code is contributed by pratham76.
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;
}
Java 语言(一种计算机语言，尤用于创建网站)
static long factorial(int n)
{
long M = 1000000007;
long f = 1;
for (int i = 1; i <= n; i++)
f = (f*i) % M; // Now f never can
// exceed 10^9+7
return f;
}
// This code is contributed by Dharanendra L V.
Python 3
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)
C
static long factorial(int n)
{
long M = 1000000007;
long f = 1;
for (int i = 1; i <= n; i++)
f = (f*i) % M; // Now f never can
// exceed 10^9+7
return f;
}
// This code is contributed by Dharanendra L V.
java 描述语言
function factorial( n)
{
let M = 1000000007;
let f = 1;
for (let i = 1; i <= n; i++)
f = (f*i) % M; // Now f never can
// exceed 10^9+7
return f;
}
添加时可以遵循相同的程序。 (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)
Python 3
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)
java 描述语言
function mod( a, m)
{
return (a%m + m) % m;
}
但是组织的规则是不同的。要在模运算中执行除法，我们需要首先理解模乘逆的概念。
模乘逆(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;
现在还有一个问题..如何求一个数的 MMI n . 求一个数的 MMI 有两种算法。第一个是扩展欧几里德算法，第二个使用费马小定理。 可以在给定的链接中找到这两种方法: 模乘逆 求模乘逆在密码学领域也有实际应用，即公钥密码和 RSA 算法。这些应用程序的计算机实现的一个好处是，存在一种非常快速的算法(扩展欧几里德算法)，可用于计算模乘逆。 参考文献: https://www . quora . com/What-确切是-print-it-模-10-9-+-7-in-competitive-programming-网站 https://discuse . codechef . com/questions/4698/of-of-module-10000007-in-competitions https://codeaccepted . WordPress . com/2008 如果你喜欢 GeeksforGeeks 并想投稿，你也可以用write.geeksforgeeks.org写一篇文章或者把你的文章邮寄到 contribute@geeksforgeeks.org。看到你的文章出现在极客博客主页上，帮助其他极客。 如果发现有不正确的地方，或者想分享更多关于上述话题的信息，请写评论。
版权属于：月萌API www.moonapi.com，转载请注明出处
