

简单数学

Copyright

本页面贡献者：LyuLumos，YanhuiJessica，Zhang1933。本页面内容遵循 MIT 协议，转载请附上原文出处链接和本声明。

素数与合数¶

素数(质数)：除了 1 和自身外，不能被其他数整除的正整数。素数只有两个因子。

合数：拥有两个以上因子的正整数。

1 既不是素数也不是合数。

试除法判断素数¶

$O(\sqrt n)$

int isPrime(int n)
{
    int i;
    for(i=2; i<=sqrt(n); i++)
    {
        if(n%i == 0)    // 如果不为素数返回0
    　　{
           return 0;
        }
    }
    return 1;    // 反之则返回1
}

素数普通筛-埃拉托斯特尼(Eratosthenes)筛法¶

基本思想：初始将所有大于等于 2 的数放在一个集合中，每次筛选后集合中剩余最小的数是质数，将它的倍数去掉。

算法结束时，没有被筛去的数就是质数。每个数要被自己所有的因子标记一遍，所以普通筛的时间复杂度为 $O(nloglogn)$

const int maxn = 1000;
bool isPrime[maxn + 5];
void getPrime()
{
    memset(isPrime, true, sizeof(isPrime));
    isPrime[1] = false; // 如果用不到1也可以不用写
    for(int i = 2; i <= maxn; i++)
        if(isPrime[i])
            for(int j = i; i * j <= maxn; j++)
                isPrime[i * j] = false;
}

素数线性筛(数论部分会涉及)¶

斐波那契数列¶

斐波那契数列（The Fibonacci sequence）的递推式如下：

$F*0 = 0, F_1 = 1, F_n = F*{n-1} + F\_{n-2}$

该数列的前几项如下：

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...$

简单性质¶

斐波那契数列增长速度趋近于 $2^n$
斐波那契数列相邻两个数之间的比值趋近于黄金分割率
前 $n$ 项之和加一等于第 $n+2$ 项
以斐波那契数列相邻两项作为输入会使欧几里德算法达到最坏复杂度

拓展¶

CUC ACM-Wiki - 数列

卡特兰数¶

Catalan 数定义如下：

$f_0=1,\,\,f_n = \sum_{i=0}^{n-1}f(i)\cdot f(n-i-1), n \in N_+$

该数列的前几项如下：

$1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012 ......$

递推公式¶

$f(n) = \frac{1}{n+1}\tbinom{2n}{n}$
$f(n) = \tbinom{2n}{n}-\tbinom{2n}{n-1}$ // 推荐
$f(n) = \sum_{i=0}^{n-1}f(i)×f(n-i-1)$
$f(n) = \frac{f(n-1)×(4n-2)}{n+1}$

应用¶

二叉树的计数问题：已知二叉树有 $n$ 个结点，求能构成多少种不同的二叉树。
括号化问题：一个合法的表达式由()包围，()可以嵌套和连接，如：(())()也是合法表达式，现给出 $n$ 对括号，求可以组成的合法表达式的个数。
划分问题：将一个凸 $n+2$ 多边形区域分成三角形区域的方法数。
出栈问题：一个栈的进栈序列为 $1,2,3,..n$ ，求不同的出栈序列有多少种。
路径问题：在 $n\cdot n$ 的方格地图中，从一个角到另外一个角，求不跨越对角线的路径数有多少种。
握手问题： $2n$ 个人均匀坐在一个圆桌边上，某个时刻所有人同时与另一个人握手，要求手之间不能交叉，求共有多少种握手方法。

整数的整除¶

最大公因子与辗转相除法¶

定理1: 设a,b,c是任意3个整数，若 $a=bq+r$ ,则有 $(a,b)=(b,r)$ 。

证明：因为 $(a,b)|r,(a,b)|b$ ,一定有 $(a,b)\leq (b,r)$

同理 $(b,r)|a,(b,r)|b$ ，所以 $(b,r)\leq (a,b)$ 。

所以可得 $(b,r)=(a,b)$

于是就有欧几里得算法(辗转相除法)。

欧几里得算法(辗转相除法)¶

求两个数的gcd,循环使用带余除法，有如下等式组：

$\begin{align} a=& q_0b+r_0,0\leq r_0 < b \nonumber \\ b=& q_1r_0+r_1 ,0\leq r_1 < r_0 \nonumber \\ r_0=& q_2r_1+r_2 ,0\leq r_2 < r_1 \nonumber \\ ... \nonumber \\ r_{n-2}=& q_{n}r_{n-1}+r_{n} ,0\leq r_{n}< r_{n-1} \nonumber \\ r_{n-1}=& q_{n+1}r_n+r_{n+1} ,r_{n+1}=0 \nonumber \end{align}$

因为有如下大小关系，余数是严格递减的: $$ b>r_0>r_1>r_2>...\geq 0 $$

再由最大公因子与辗转相除法定理1可得等式链：

$\begin{align} (a,b)=& \nonumber\\ (b,r_0)=& \nonumber\\ (r_0,r_1)=& \nonumber\\ (r_1,r_2)=& \nonumber\\ ...& \nonumber\\ (r_n,0)=& r_n \nonumber \end{align}$

最后 $r_n$ 即为所求。其思想就是把一个大的问题转化成一个小的问题来求解。

求gcd的代码：

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}

裴蜀定理¶

又称贝祖定理,任意a,b不全为0的整数,存在整数x,y，使得:

$ax+by=(a,b)$

可以将朴素欧几里得算法回带带出x,y证明其正确性。这里说下面递归代码求解x,y的原理。

证明：

设有 $$ ax_0+by_0=(a,b) $$ 继续使用带余除法可得: $$ bx_1+(a\%b)y_1=(b,a\%b) $$

由大公因子与辗转相除法定理1可得： $$ (a,b)=(b,a\%b) $$

于是带入得到：

$\begin{align} ax_0+by_0=& bx_1+(a\%b)y_1 \\ =& bx_1+(a-a/b*b)y_1 \\ =& ay_1+b(x_1-a/b*y_1) \end{align}$

于是可得递推关系：

$x_0=y_1 \\ y_0=x_1-a/b*y_1$

所以就可以在算gcd回溯的时候反向递推，写出如下代码：

ll exgcd(ll a,ll b,ll &x,ll &y){
    if(a==0&&b==0)return -1;
    if(b==0){
        x=1;y=0;
        return a;
    }
    ll ans=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return ans;
}

变量x和y中存储了方程 $a*x+b*y=(a,b)$ 的一组整数解;函数的返回值是gcd(a,b),若返回-1,则无解;

同余式¶

定义：给定一个正整数 m,若用 m 分别去除两个整数 a，b 所得的余数相同，则称 a 与 b 模 m 同余，记为: $a \equiv b\ (mod\ m)$
定理 1：整数 a,b 模 m 同余的充要条件是 $m|(a-b)$ 。

证明:

设 $a=k_1m+r_a,b=k_2m+r_b,0\leq r_a,r_b < m$ 。

1.证：若 a,b 模 m 同余，则可以推出 $m|(a-b)$ 。

因为 a,b 模 m 同余，则 $r_a=r_b$ ,于是 $a-b=(k_1-k_2)m$ ,即 $m|(a-b)$

2.证：若 $m|(a-b)$ ，则 a,b 同余。

因为 $m|(a-b)$ ，即 $m|[(k_1-k_2)m+(r_a-r_b)]$ ,所以 $m|(r_a-r_b)$

因为有 $-m<r_a-r_b<m$ ,所以只有 $r_a=r_b$ 。

同余式的一些性质：¶

1. $a \equiv b(mod\ m), b\equiv c (mod \ m), 则 a\equiv c (mod \ m)$ .

2. $设ad\equiv bd(mod\ m)$ ,若 $(d,m)=1$ ，则 $a\equiv b(mod\ m)$ 。

证明:

根据同余式定理 1, 有 $m|d(a-b)$ , 因为 $(d,m)=1$ ,则 $m|(a-b)$ 。

3.设 $a\equiv b(mod\ m)$ ,若 d 是 a,b,m 的公因子，则 $\frac{a}{d}\equiv \frac{b}{d}(mod\ \frac{m}{d})$ 。

证明：

若 $a\equiv b(mod\ m)$ ,则 $a=m*k+b$ ,d 是 a,b,m 的公因子,有 $\frac{a}{d}=\frac{m}{d}*k+\frac{b}{d}$ ,所以 $\frac{a}{d}\equiv \frac{b}{d}(mod\ \frac{m}{d})$ 。

4.若 $a \equiv b(mod\ m_i),i=1,2,...k$ ，则 $a \equiv b(mod [m_1,m_2,..m_k])$ 。

证明：

若 $a\equiv b(mod\ m_i)$ ,即 $m_i|(a-b),i=1,2..k$ ,可以推出 $a-b$ 是 $m_i$ 的公倍数，所以 $[m_1,m_2,...m_k]|(a-b)$ 。故 $a \equiv b(mod [m_1,m_2,..m_k])$ 。

5.若 $a \equiv b(mod\ m)$ ,则 $(a,m)=(b,m)$ 。

证明：

若 $a\equiv b(mod\ m)$ ,则存在 $k \in Z$ ,使得 $a=km+b$ 。因为 $(a,m)|a$ , $(a,m)|m$ ,因为 $b=a-km$ ,所以有 $(a,m)|b$ ,即 $(a,m)$ 是 b 和 m 的公因子，所以有 $(a,m)\leq (b,m)$ 。同理可证 $(b,m)\leq (a,m)$ 。所以就得到 $(a,m)=(b,m)$ 。

同时上面证明可以得到一个最大公因数的结论：若 $a=km+b$ ,则 $(a,m)=(b,m)$ 。

剩余类¶

定义 1:设 m 是一个正整数，任一个整数除以 m 所得的余数是 0，1，2，...m-1 中的某一个。用某一个集合符号 $[i](0\leq i \leq m-1)$ 表示所有模 m 余数为 i 的集合，该集合中元素的形式为 $a=km+i,k\in Z$ 。任何一个整数必属于某个 $[i]$ 。 $Z$ 的子集合 $[i]$ 称为整数模 m 的一个剩余类。集合 $[0],[1],...[m-1]$ 构成模 m 的完全剩余类，用 $Z_m=\{[0],[1],...,[m-1]\}$ 表示,通常简记为 $Z_m=\{0,1...,m-1\}$ 。

定义 2: 如果模 m 的一个剩余类中的数与 m 互素，就称这个剩余类为与模 m 互素的剩余类。在与 m 互素的所有剩余类中，各取一数所组成的集合叫做模 m 的一组缩系(既约剩余系)。
定理 1:只要某个剩余类中的一个数与 m 互素，则该剩余类的所有其他数也与 m 互素。

证明:同余式性质 5。

定理 2:设 $a_1,a_2,...a_{\varphi(m)}$ 是模 m 的一组缩系，若 $(k,m)=1$ ,则

$ka_1,ka_2,...ka_{\varphi(m)}$

也是模 m 的一组缩系。 $\varphi(m)$ 表示 m 的欧拉函数，定义见欧拉函数节。

证明：因为 $(a_i,m)=1,(k,m)=1$ ，则

$(ka_i,m)=1,1\leq i \leq \varphi(m)$

因为 $a_i$ 与 m 质因子分解后不包含公共的质因子， $k$ 与 $m$ 质因子分解后不包含公共的质因子，所以乘起来还是不包含公共的质因子。

因为 $m\nmid (a_i-a_j),i\neq j$ 。有 $m\nmid k(a_i-a_j)$ ~~(可以用质因子分解的角度想)~~。所以

$ka_i \not\equiv ka_j(mod\ m)$

因为个数没变，模下来两两之间结果不相同且gcd为1,所以 $k_{a_1},k_{a_2},..,k_{a_\varphi(m)}$ 是模 m 的一组缩系。

定理3: 设m的一组完全剩余系为： $a_1,a_2,...a_{m-1}$ ,若 $(k,m)=1$ ,则 $ka_1,ka_2,...,ka_{m-1}$ 也是m的一组完全剩余系。

证明：

用定理2的第二步同理证明可得。

欧拉函数¶

定义 1:欧拉函数 $\varphi (m)$ 表示整数序列 0,1,2,...,m-1 中与 m 互素的数的个数。规定 $\varphi (1)=1$ 。当 m 素数时，显然有 $\varphi (m)=m-1$ 。

欧拉定理¶

设 $m\in Z^+,(k,m)=1$ ，则：

$k^{\varphi (m)}\equiv 1(mod\ m)$

证明：设整数 $a_1,a_2,...a_{\varphi(m)}$ 是模 m 的一组缩系，因为 $(k,m)=1$ ,则由剩余类定理 2，知 $ka_1,ka_2..ka_{\varphi(m)}$ 也是模 m 的一组缩系。

所以：

$a_1a_2...a_{\varphi(m)}\equiv ka_1ka_2...ka_{\varphi(m)}(mod\ m)$

由同余式性质 2 可得： $k^{\varphi(m)}\equiv 1(mod\ m)$

根据欧拉定理可以得到费马小定理：

费马小定理¶

欧拉定理特殊情况：若 p 为素数， $(a,p)=1$ ,则 $a^{p-1}\equiv 1(mod\ p)$ 。

可得到:若 p 为素数， $(a,p)=1$ ,a 在模 p 下的逆元为 $a^{p-2}(mod\ m)$ 。(逆元定义见逆元节)。

欧拉函数的一些定理：¶

定理一: 如果 p 是质数，并且 $k \geq 1$ 则有：

$\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)=p^k(1-\frac{1}{p})$

证明：因为 p 是质数，对于 $1\leq m\leq p^k$ 能让 $gcd(p^k,m)>1$ 的 m 的条件只有让 m 是 p 的倍数，也就是 $m \in \{p,2p,3p,...p^{k-1}p=p^k\}$ 。这样的数一共有 $p^{k-1}$ 个。所以剩下互素的就有 $p^k-p^{k-1}$ 个。

定理二： 欧拉函数是积性函数。如果 m,n 互素即 $gcd(n,m)=1$ ，则有 $\varphi(m)\varphi(n)=\varphi(mn)$

证明：

将 $0,1...mn-1$ 写成下面这种类似剩余类的形式：

$\begin{matrix} 0 & m & 2m &...& (n-1)m \\ 1 & m+1 & 2m+1 &...& (n-1)m+1 \\ 2 & m+2 & 2m+2 &...& (n-1)m+2\\ ... \\ m-1 & 2m-1 & 3m-1& ...& mn-1 \end{matrix}$

由剩余类定理 1 可知，有 $\varphi(m)$ 行与 m 互素。然后需要证这些行中与 n 互素的数有多少。

因为 $0，1，2，...n-1$ 是模 n 的一组完全剩余系。因为 $(m,n)=1$ ,由剩余类定理 2第二步的证明思路可证 $0，m，2m...(n-1)m$ 也是模 n 的一组完全剩余系。

因为 $0+a,m+a,2m+a,...,(n-1)m+a,0\leq a \leq n-1$ 也是模 n 的一组完全剩余系(相当于每个数都往后循环偏移 a 个数)。

所以在与 m 互素的行(同时也是所有的行)中有 $\varphi(n)$ 个数与 n 互素。

所以在 nm 个数中一共有 $\varphi(m)\varphi(n)$ 个数与 nm 互素。得证。

定理三：

将 n 质因子分解得到 $n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$ ， $p_i$ 为质数， $a_i$ 为正整数，则有：

$\varphi(n)=p_1^{a_1-1}(p_1-1)p_2^{a_2-1}(p_2-1)...p_k^{a_k-1}(p_k-1)$

证明：由欧拉函数定理二可得:

$\varphi(n)=\varphi(p_1^{a_1})\varphi(p_2^{a_2})...\varphi(p_k^{a_k})$

再由欧拉函数定理 1 把 $\varphi(p_i^{a_i})$ 展开相乘可得上述结论。

线性同余方程¶

形如 $ax\equiv b(mod\ m)$ 的等式称为线性同余方程。

定理 1: 设 $a,b\in Z,m\geq0$ ,若 $(a,m)=1$ ,则同余式

$$ ax\equiv b(mod m) $$ 在 $0 \leq x \leq m-1$ 的范围内恰有一个解。

证明：在模m的一组完全剩余系中： $$ 0,1,2,...m-1 $$

有一个数恰好与b同余。

由剩余系定理3可知： $$ 0,a,2a,...a(m-1) $$

也是模m的一组完全剩余系,且恰好有一个 $xa$ 与b同余。那个x即为所求。

定理 2 : 同余方程 $ax\equiv b(mod\ m)$ 有解的充要条件是 $(a,m)|b$ 。

证明：

证明若同余方程 $ax\equiv b(mod\ m)$ 有解，则 $gcd(a,m)|b$ 。

设同余方程 $ax\equiv b(mod\ m)$ 的解为 $x_0$ ,于是存在 $k\in Z$ ,有 $b=ax_0+my$ 。因为 $gcd(a,m)|a,gcd(a,m)|m$ ,所以 $gcd(a,m)|b$ 。

证明若 $gcd(a,m)|b$ ,则同余方程 $ax\equiv b(mod\ m)$ 有解。

设 $d=gcd(a,m)$ 。有 $gcd(\frac{a}{d},\frac{m}{d})=1$ ~~(可以用两个数质因子分解与gcd的关系的角度来想其正确性)~~,由线性同余方程定理1可得同余式: $$ \frac{a}{d}x\equiv \frac{b}{d}(mod \frac{m}{d}) \tag{1} $$

有解。设方程组(1)的解为 $x_0$ , $x\equiv x_0(mod\ \frac{m}{d})$ 也是(1)的解。将(1)写成等式,即存在 $$ \frac{a}{d}x_0+\frac{m}{d}y=\frac{b}{d} $$ 两边同乘d有: $$ ax_0+my=b $$ 即： $$ ax_0\equiv b( mod m) $$ 所以 $x_0$ 即为所求。同时，上述证明可以说明，在模m下，方程有d个解，其分别是 $x_0,x_0+\frac{m}{d},x_0+2\frac{m}{d},...x_0+(d-1)\frac{m}{d}$ 。

最小正整数解可以通过表达式 $x_0=(x\%\frac{m}{d}+\frac{m}{d})\%\frac{m}{d}$ 求出。

所以只要我们有办法求出一组解，就可以求出所有的解，于是就有了下面这种思路。

线性同余方程求解方法：

用线性同余方程定理1排除无解的情况，现在来考虑有解的情况。首先将 $ax\equiv b(mod\ m)$ 方程改写为 $a*x+m*y=b$ 的形式,然后使用拓展欧几里德求出一组特解 $x_1,y_1$ 满足 $ax_1+my_1=(a,m)$ 。然后在原方程两边同时除以 $(a,m)$ 并乘上b得到： $$ \frac{abx_1}{(a,m)}+\frac{mby_1}{(a,m)}=b $$

就得到了方程 $ax_0+my_0=b$ 的一组解也就是同余方程 $ax_0\equiv b(mod\ m)$ 的一组解。知道了一组解，剩下的解就可以根据线性同余方程定理2第二个证明求出其他解了。

代码:

//解同余方程$ax0\equiv b(mod m)$中最小的x0,若无解返回false
bool ModularEqu(int a,int b,int m,int &x0){
    int x,y,k;
    int d=exgcd(a,m,x,y);
    if(b%d==0){
        x0=x*(b/d)%m;k=m/d;x0=(x0%k+k)%k;
        return true;
    }
    return false;
}

逆元¶

用来解决取模条件下除法的问题。

定义:

如果一个线性同余方程有 $ax\equiv 1(mod\ m)$ ，则称x为 a在模m下的的逆元，记作 $a^{-1}$ 。

1.扩展欧几里得求逆元：

使用条件：线性同余方程有解条件，即: $(a,m)=1$ 。

和求解同余方程为一个原理。

2.快速幂求逆元：

使用条件：模数是素数。

用得最多，求解原理见费马小定理节。

代码就是快速幂的代码。

参考资料：

姜正涛.《信息安全数学基础》[M].北京:电子工业出版社,2017.
Euler's totient function - Wikipedia
oi wiki 数学部分

简单数学实战¶

找规律¶

1 1 2 3 5 8 13 ...
1 1 2 5 14 ...
1 5 10 10 5 1
1 4 10 20 35 56 ...

结论¶

有限项数列都可以用公式表示，比如 Lagrange 插值公式就可以求出通项。
公式显然不止一个。

所以猜测是有风险的。

举个栗子¶

1，2，3，4，5，？

显然答案是 126，因为 $a_n = (n-1)(n-2)(n-3)(n-4)(n-5)+n$ 。

但其实它有很多种答案，比如 $a_n =C \cdot (n-1)(n-2)(n-3)(n-4)(n-5)+n, C为常数$ 。

反例¶

Codeforces 656A - Da Vinci Powers

找规律，输入3输出8，输入10输出1024，输入13输出8092。

需要用下面介绍的 OEIS 解决。

OEIS¶

The On-Line Encyclopedia of Integer Sequences® (OEIS®)

包含了绝大部分数列，只能在网络比赛中使用。

例题

题目来源：2020 牛客寒假算法小白训练营

一个游戏，人物攻击力为0-10，怪物的生命值为10，每次攻击对怪物以均等的1/11的概率，随机造成0，1，2……10中之一点数的伤害，怪物的体力达到0或更低时视为击败，问击败怪物的平均攻击次数？

设当怪物血剩余 $n$ 时攻击次数的期望为 $a_n$ 。则显然 $a_0＝0$ ，考虑 $n < 1$ ，此时肯定要先打一次。打完后有 $\frac{11-n}{11}$ 的概率怪兽死亡，另外有 $\frac{1}{11}$ 的概率回到 $a_1-a_n$ 中的一种情况。故有 $a_n=1+\frac{1}{11}(a_1+...+a_n)$ 。令 $Sn=a_1+...a_n$ ，则有 $a_{n}=1+\frac{1}{11}S_{n}$ 。解得 $a_n=(\frac{11}{10})^n$ 。本题答案为 $1.1^{10}$ 。

具体计算过程

$a_{n}=1+\frac{1}{11}S_{n}$

$a_{n-1}=1+\frac{1}{11}S_{n-1}$

相减 $a_n-a_{n-1}=\frac{1}{11}*a_n$

$a_n=\frac{11}{10}a_{n-1}(n >0)$

当怪物血剩余 $n$ 时攻击次数的期望为 $a_n$ 。则显然 $a_0＝0$

$n = 1$ 代入解得

$a_1=\frac{11}{10}$ 则 $a_n=(\frac{11}{10})^n$