跳转至

数学基础知识

最大公约数

多个整数共有约数中最大的一个

素数

又称质数,指除了本身和1之外无法被其他自然数整除的自然数(非负整数),与其对应的称之为合数

若多个整数的最大公约数是1,则称它们为互质或互素,比如4和7

取模

取模运算,也叫取余运算,但准确来讲取模(Mod)和取余(Rem)还是有些不同的

通常可表示为:x%y,取余的结果符号总会和x一致,取模的结果则会一直和y一致(比如Python中:7%-2=-1

在整数运算中,通常将运算结果取模来防止整数溢出

比如整数长度如果为32位,可表示范围:-2^31 ~ 2^31-1,即如果运算结果超过2147483647则会溢出。

虽然有些语言(比如Python)支持存储无限大数字的数据类型,但数据类型大小并不是唯一的问题。
随着数字大小的增加,对它们执行数学运算所需的时间也会增加。

为此我们需要选取一个合适的模数M,它需要满足以下条件

  1. M要在整数长度范围内,且还要足够大
  2. M必须为素数,以保证取模结果不为0

第一个10位素数:10^9+7,恰好符合这两个标准,虽然它并不是唯一的,但通常是用的最多的。1


最后更新: 2021-09-12