算法-数学

包括了离散数学、线性代数方面的一些基础知识。

质数

对于一个足够大的整数 $N$，不超过 $N$ 的质数大约有 $N/lnN$ 个，即每$lnN$ 个数中有一个质数

质数的判定

使用试除法判定质数，显然，对于一个合数 $N$，存在一个 $[2, \sqrt{N}]$ 之间的数可以整除 $N$。

bool is_prime(int n)
{
    if (n < 2)
        return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
            return false;
    return true;
}

筛质数

Eratosthenes筛法
任意整数 $x$ 的倍数 $2x,3x···$ 都不是质数。

从 2 开始，从大到小扫描每个数 $x$，将 $2x,3x,···,[N/x]\times x$ 标记为合数。若扫描到一个数未被标记时，则该数为质数。若已被标记，显然其倍数也被标记了其本身的质数标记，故不需要标记其倍数。

同时，显然，对于一个数 $x$ 的一对约数 $a,b\ (1<a<b, a\times b = x)$，其必定首先被 $a$ 标记，故我们不需要在扫描 $b$ 时标记 $x$。这一情况对于 $x \in [2b, ··· (b-1)b]$ 都适用，所以在标记时，直接从 $b^2$ 开始标记即可。

该筛法的时间复杂度为 $O(nloglogn)$。

bool st[N];
void primes(int n)
{
    memset(st, 0, sizeof(st));
    for (int i = 2; i <= n; i++)
    {
        if (st[i])
            continue;
        for (int j = i; j * i <= n; j++)
            st[i*j] = true;
    }
}

线性筛法
线性筛法通过“从小到大积累质因子”的方法标记每个合数，即让 12 只有 6*2 一种产生方式。设 线性筛法如下：

1. 依次考虑 $2\sim N$ 之间的每个数 $i$。
2. 若未被标记，则为质数
3. 扫描所有质数。当扫描到第一个质数 $p_i$ 满足 $i \ mod\ p_i = 0$ 时，说明 $p_i$ 是 i 的最小质因子，跳出循环。

bool st[N];
int prime[N], m = 0;
void primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
            prime[m++] = i;
        for (int j = 0; j < m && prime[j] * i <= n; j++)
        {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
}

质因数分解

算术基本定理
任意一个大于 1 的正整数都能唯一分解为有限个质数的乘积，可写作：

$$N=p_1^{c_1}p_2^{c_2}···p_m^{c_m}$$

其中 $c_i$ 都是正整数，$p_i$ 都是质数，且满足 $p_1<p_2<···<p_m$。

试除法
扫描 $2\sim \lfloor\sqrt{N}\rfloor$ 的每个数 $d$，若 $d$ 能整除 $N$，则从 $N$ 中除掉所有的因子 $d$，同时累加计算 $d$ 的个数。

因为一个合数因子一定在扫描到这个合数之间就被除掉了，所以所有 $d$ 一定是质数。最终得到了质因数分解的结果，时间复杂度为 $O(\sqrt{N})$。

int p[N], c[N], m = 0;
void divide(int n)
{
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            p[++m] = i, c[m] = 0;
            while (n % i == 0)
                n /= i, c[m]++;
        }
    }
    if (n > 1)
        p[++m] = n, c[m] = 1;
}

约数

若 $d$ 能整除 $n$，称 $d$ 为 $n$ 的约数，记为 $d|n$。

算术基本定理的推论
在算术基本定理中，若正整数 $N$ 被唯一分解为 $N=p_1^{c_1}p_2^{c_2}···p_m^{c_m}$，其中 $c_i$ 都是正整数，$p_i$ 都是正数，且满足 $p_1<p_2<···<p_m$，则 $N$ 的正约数集合可写作：

$$\{p_1^{b_1}p_2^{b_2}···p_m^{b_m}\}，其中 0\le b_i\le c_i$$

$N$ 的正约数个数为：

$$(c_1+1)\times(c_1+1)\times···\times(c_m+m)=\prod_{i=1}^m(c_i+1)$$

$N$ 的所有正约数的和为：

$$(1+p_1+p_1^2+···+p_1^{c_1})\times ···\times(1+p_m+p_m^2+···+p_m^{c_m})=\prod_{i=1}^m(\sum_{j=0}^{c_i}(p_i)^j)$$

求 N 的正约数集合：试除法

显然，除完全平方数之外的约数成对出现，且在 $\sqrt{N}$ 两侧。故枚举 $d=1\sim \sqrt{N}$即可。

int factor[N], m = 0;
for (int i = 1; i * i <= n; i++)
{
    if (n % i == 0)
    {
        factor[++m] = i;
        if (i != n / i)
            factor[++m] = n / i;
    }
}

推论
一个整数 $N$ 的约数个数上界为 $2\sqrt{N}$。

求 1∼N 每个数的正约数集合——倍数法

对于每个数 $d$，$1\sim N$ 中以 $d$ 为约数的数就是 $d$ 的倍数，$d,2d,3d,···,\lfloor N/d\rfloor *d$。

vector<int> factor[N];
for (int i = 1; i <= n; i++)
    for (int j = 1; i * j <= n; j++)
        factor[i*j].push_back(i);

最大公约数

定义
若自然数 $d$ 同时是自然数 $a$ 和 $b$ 的约数，则称 $d$ 是 $a$ 和 $b$ 的公约数。在所有 $a$ 和 $b$ 的公约数中最大的一个，称为 $a$ 和 $b$ 的最大公约数，记为 $gcd(a,b)$。

若自然数 $d$ 同时是自然数 $a$ 和 $b$ 的倍数，则称 $d$ 是 $a$ 和 $b$ 的公倍数。在所有 $a$ 和 $b$ 的公倍数中最大的一个，称为 $a$ 和 $b$ 的最大公倍数，记为 $lcm(a,b)$。

定理

$$\forall a, b \in \mathbb{N},\ gcd(a,b)*lcm(a,b)=a*b$$

欧几里得算法

$$\forall a,b \in \mathbb{N},\ gcd(a,b)=gcd(b,a \ mod \ b)$$

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

时间复杂度约为 $O(log(a+b))$。

互质与欧拉函数

定义
$\forall a,b\in \mathbb{N}$，若 $gcd(a,b)=1$，则称 $a$，$b$ 互质。

欧拉函数
$1\sim N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $\varphi(N)$。若在算术基本定理中，$N=p_1^{c_1}p_2^{c_2}···p_m^{c_m}$，则：

$$\varphi(N)=N*\cfrac{p_1-1}{p_1}*\cfrac{p_2-1}{p_2}*···*\cfrac{p_m-1}{p_m}=N*\prod_{质数p|N}(1-\cfrac{1}{p})$$

推论

1. $\forall n>1，1\sim n$ 中与 $n$ 互质的数的和为 $n*\varphi(n)/2$ 。
2. 若 $a,b$ 互质，则 $\varphi(ab)=\varphi(a)\varphi(b)$ 。
3. 设 $p$ 为质数，若 $p\mid n$ 且 $p^2\mid n$，则 $\varphi(n)=\varphi(n/p)*p$ 。
4. 设 $p$ 为质数，若 $p\mid n$ 但 $p^2\nmid n$，则 $\varphi(n)=\varphi(n/p)*(p-1)$ 。
5. $\sum_{d\mid n}\varphi(d)=n$ 。

// 求一个数的欧拉函数
int phi(int n)
{
    int ans = n;
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
        {
            ans = ans / i * (i - 1);
            while (n % i == 0)
                n /= i;
        }
    if (n > 1)
        ans / n * (n - 1);
    return ans;
}

// 利用筛法求 1 ~ n 的欧拉函数
int phi[N];
void eular(int n)
{
    for (int i = 2; i <= n; i++)
        phi[i] = i;
    for (int i = 2; i <= n; i++)
        if (phi[i] == i)
            for (int j = i; j <= n; j++)
                phi[j] = phi[j] / i * (i - 1);
}

bool st[N];
int pri[N / 10], tot = 0;
int phi[N];
void eular(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
            pri[++tot] = i, phi[i] = i - 1;
        for (int j = 1; j <= tot && pri[j] * i <= n; j++)
        {
            int v = pri[j] * i;
            st[v] = true;
            if (i % pri[j] == 0)
            {
                phi[v] = phi[i] * pri[j];
                break;
            }
            else
                phi[v] = phi[i] * (pri[j] - 1);
        }
    }
}

同余

定义
若整数 $a$ 和整数 $b$ 除以正整数 $m$ 的余数相等，则称 $a$，$b$ 模 $m$ 同余，记为 $a\equiv b\ (mod \ m)$。

同余类与剩余系
对于 $\forall a\in[0,m-1]$，集合 $\{a+km\}(k\in\mathbb{Z})$ 的所有数模 $m$ 同余，余数都是 $a$。该集合称为一个模 $m$ 的同余类，简记为 $\overline{a}$。

模 $m$ 的同余类一共有 $m$ 个，分别为 $\overline{0},\overline{1},\overline{2},···,\overline{m-1}$。它们构成 $m$ 的完全剩余系。

$1\sim m$ 中与 $m$ 互质的数代表的同余类共有 $\varphi(m)$，他们构成 $m$ 的完全剩余系。

$1\sim m$ 中与 $m$ 互质的数代表的同余类共有 $\varphi(m)$ 个，它们构成 $m$ 的简化剩余系，例如，模 $10$ 的简化剩余系为 $\{\overline{1},\overline{3},\overline{7},\overline{9}\}$。简化剩余系关于模 $m$ 乘法封闭。

费马小定理
若 $p$ 是质数，则对于任意整数 $a$，有 $a^p\equiv a \ (mod\ p)$。

欧拉定理
若正整数 $a,n$ 互质，则 $a^{\varphi(n)}\equiv 1 \ (mod\ n)$，其中 $\varphi(n)$ 为欧拉函数。

欧拉定理的推论
若正整数 $a,n$ 互质，则对于任意正整数 $b$，有 $a^b\equiv a^{b\ mod\ \varphi(n)}(mod\ n)$。

扩展欧几里得算法

Bézout定理
对于任意整数 $a,b$，存在一对整数 $x,y$，满足 $ax+by=gcd(a,b)$。

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

对于更为一般的方程 $ax+by=c$，当且仅当 $gcd(a,b)\mid c$ 时有解。

乘法逆元

若整数 $b,m$ 互质，并且 $b\mid a$，则存在一个整数 $x$，使得 $a/b\equiv a*x(mod\ m)$。称 $x$ 为 $b$ 的模 $m$ 乘法逆元，记为 $b^{-1}(mod\ m)$。

因为 $a/b\equiv a*b^{-1}\equiv a/b*b*b^{-1}(mod\ m)$，所以 $b*b^{-1} \equiv 1(mod\ m)$。

如果 $m$ 是质数（此时我们用符号 $p$ 代替 $m$）并且 $b<p$，根据费马小定理， $b^{p-1}\equiv 1(mod\ p)$，即 $b*b^{p-2}\equiv 1(mod\ p)$。因此，当模数 $p$ 为质数时，$b^{p-2}$ 即为 $b$ 的乘法逆元。

线性同余方程

给定整数 $a,b,m$，求一个整数 $m$ 满足 $a*x\equiv b\ (mod\ m)$。

原式等价于 $a*x-b$ 是 $m$ 的倍数，不妨设为 $-y$ 倍，则可以改写为 $a*x+m*y=b$，有解当且仅当 $gcd(a,m)\mid b$。

组合计数

性质

1. $C_n^m=C_n^{n-m}$
2. $C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$
3. $C_n^0+C_n^1+C_n^2+···+C_n^n=2^n$

求法
预处理阶乘与阶乘的逆元，使用定义公式计算。

// 快速幂
int qmi(int x, int n)
{
    int res = 1;
    while (n)
    {
        if (n & 1)
            res = (long long)res * x % MOD;
        x = (long long)x * x % MOD;
        n >>= 1;
    }
    return res;
}

fact[0] = infact[0] = fact[1] = infact[1] = 1
for (int i = 1; i <= N; i++)
{
    fact[i] = (long long)fact[i - 1] * i % MOD;
    infact[i] = (long long)infact[i - 1] * qmi(i, MOD - 2) % MOD;
}

c(a, b) = (long long)fact[a] * infact[a-b] % MOD * infact[b] % MOD;

当 $a,b$ 很大但是模数很小时，可以使用Lucas定理：

$$C_a^b\equiv C_{a\ mod\ p}^{b\ mod\ p}\cdot C_{a/p}^{b/p}(mod\ p)$$

简化计算。

概率和数学期望

博弈论

NIM博弈

给定 $n$ 堆物品，第 $i$ 堆物品有 $A_i$ 个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取先手策略，问先手能否必胜。

这种游戏是 NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。若存在某种行动使得行动后对手面临必败局面，这一局面称为必胜。NIM博弈只有先手必胜和必败两种情况。

定理
NIM博弈先手必胜，当且仅当 $A_1\ xor\ A_2\ xor\ ···\ xor A_n \neq 0$。

证明
所有物品都被取光是一个必败局面，此时有 $A_1\ xor\ A_2\ xor\ ···\ xor A_n = 0$。

对于任意一个局面，设异或和为 $x$。若其非零，设其二进制表示下最高位的 $1$ 在第 $k$ 位，此时必定存在一个 $A_i$ 使得第 $k$ 位也是 $1$，此时有 $A_i\ xor\ x < A_i$，于是取走 $A_i$ 的物品使之变为 $A_i\ xor\ x$，则所剩石子异或和为 $0$。

若 $x$ 为零，无论如何取物品，得到的局面下异或和都不为零。

公平组合游戏ICG

若一个游戏满足

1. 由两名玩家交替行动
2. 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关
3. 不能行动的玩家判负

则称该游戏为一个公平组合游戏。NIM博弈属于公平组合游戏。

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子，两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。

该游戏被称为有向图游戏。任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点。

Mex运算

设 $S$ 表示一个非负整数集合。定义 $mex(S)$ 为求出不属于集合 $S$ 的最小非负整数运算，即：

$$mex(S) = min\{x|x\in N, x \notin S \}$$

SG函数

在有向图游戏中，对于每个节点 $x$，设从 $x$ 出发共有 $k$ 条有向边，分别到达节点 $y_1,y_2,···,y_k$，定义 $SG(x)$ 为 $x$ 的后继节点 $y_1,y_2,···y_k$的SG函数值构成的集合再执行 $mex$ 运算的结果，即：

$$SG(x)=mex({SG(y_1),SG(y_2),···,SG(y_k)})$$

特别地，整个有向图游戏 $G$ 的SG函数值被定义为有向图游戏起点 $s$ 的SG函数值，即 $SG(G)=SG(s)$。

有向图游戏的和

设 $G_1,G_2,···,G_m$ 是 $m$ 个有向图游戏，定义有向图游戏 $G$，它的行动规则是任选某个有向图游戏 $G_i$，并在 $G_i$ 上行动一步。$G$ 被称为有向图游戏 $G_1,G_2,···,G_m$ 的和。有向图游戏的和的SG函数值等于它包含的子游戏SG函数值的异或和，即

$$SG(G)=SG(G_1)\ xor\ SG(G_2)\ xor\ ···\ xor\ SG(G_m)$$

有向图游戏的某个局面必胜，当前仅当该局面对应节点的SG函数值大于0；必败，当且仅当该局面对应节点的SG函数值等于0。