@WangYixu 2018-06-14T13:09:50.000000Z 字数 8676 阅读 823

OI 数学 笔记 算法

数学学习笔记

数论

1.简介

主要研究整数的性质

2.整除

定义2.1：对于整数 $n, m$ ，若 $m \ne 0$ 且 $\exists k \in Z,km=n$ ，则称 $m$ 整除 $n$ ，记作 $m \mid n$ .

整除的性质

$a\mid a\ (a \ne 0)$
$a \mid b,b\mid a \iff a =\pm b$
$a\mid b, b\mid c \Rightarrow a\mid c$
$b\ne 0, a\mid b \Rightarrow |a|\le |b|$
$b\mid a \iff bm\mid am$
$a\mid b, a\mid c \iff \forall x,y,\ \ a\mid bx + cy$

3.素数

定义3.1： $n \in Z^+,n>1,\forall m \in (1,n),m \nmid n$ ，则n为质数，否则n为合数.
定理3.2： $\sum \limits_{isprime(x)}^{n} \sim \displaystyle\frac{x}{ln\ x}$ （素数定理）
定理3.3：对于 $\forall n\in Z^+, n > 1,n = p_1p_2\cdots p_m$ 等号右边的式子唯一.（算数基本定理）

也可写作 $n=p_1^{r_1}p_2^{r_2}\cdots p_m^{r_m}$ .

素数判定

0.枚举所有 $2$ 到 $n-1$ 的整数，检查是否为因数，复杂度 $O(n)$ .
1.枚举 $2$ 到 $\sqrt{n}$ 的所有正整数，检查是否为因数， $O(\sqrt{n})$ .
2.枚举 $2$ 到 $\sqrt{n}$ 的所有素数，检查是否为因数， $O(\displaystyle\frac{\sqrt{n}}{ln\sqrt{n}})$ .
3.Miller-Rabin.

质因数分解

枚举 $2$ 到 $\sqrt{n}$ 的所有质数，不断试除至除净.

最后可能会剩一个大的素因子.

4.筛法

埃氏筛

notp[1] = 1;
for (int i = 2; i <= n; i ++) 
    if (!notp[i]) 
        for (int j = i * i; j <= n; j += i) 
            notp[j] = 1;

线性筛

约定每个数只被它的最小质因子筛去。

notp[1] = 1;
for (int i = 2; i <= n; i ++) {
    if (!notp[i]) pri[++ psz] = i;
    for (int j = 1; j <= psz; j ++) {
        int k = i * pri[j];
        if (k > n) break ;
        notp[i * pri[j]] = 1;
        if (i % pri[j] == 0) break;
        //pri[j]是i的素因子，那么pri[j+1]*i的最小素因子不是pri[j+1]，按照约定，跳出循环。
    }
}

区间筛

给定 $l, r(1\le l \le r \le 10^9, r-l\le10^5$ ，求 $[l,r]$ 范围内的素数。

\\预先筛好[1,sqrt(r)]范围内的素数
for (int i = 1; i <= psz; i ++) {
    int p = pri[i];
    for (int j = (l - 1) / p + 1/*防止下标小于0*/; j <= r / p; j ++) 
        notp[j * p - l] = 1;
}

5.mod运算

定理5.1： $n, m\in Z,m\ne0,\exists(q,r),n = qm + r\land 0\le r < |m|$ .（除法定理）
定义5.2：称5.1中的 $q = \lfloor n/m \rfloor$ 为除法的商， $r = n \bmod m$ 为余数.

$n \bmod m = n - m\lfloor n/m\rfloor,m\ne 0$ .

6.GCD

定义6.1：两个数 $n,m$ 的最大公约数是能整除他们两者的最大整数。记为 $\gcd(m, n)$ 或 $(m, n)$ .

欧几里得算法

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

定理6.2： $\forall a, b\in Z ,d = (a,b),ax+by=c$ 有整数解 $\iff d\mid c$ （裴蜀定理）
引理6.2.1： $ax+by$ 的最小正值为 $\gcd(a,b)$ .
推论6.2.2： $\forall a,b,d\mid a\land d\mid b \Rightarrow d\mid \gcd(a,b)$ .
推论6.2.3： $(a,b) = 1 \iff \exists x,y,ax+by=1$ .
推论6.2.4： $a\mid bc \land (a,b)=1\Rightarrow a\mid c$ .

证明：

$(a,b) = 1 \Rightarrow am + bn = 1\Rightarrow acm+bcn = c$

$a\mid ac \land a\mid bc \Rightarrow a\mid acm+bcn \Leftrightarrow a\mid c$

推论6.2.5：质数 $p\mid ab \Rightarrow p\mid a \lor p\mid b$ .

推广： $p\mid a_1a_2\cdots a_k \Rightarrow \exists a_i,p\mid a_i$

例题 GCD and LCM

如果 $G\nmid L$ ，不合法，输出零。

对 $L$ 和 $G$ ，分别唯一分解，对于某个质因子 $p_i$ ，其指数为 $k_L,k_G$ ，如果 $k_L=k_G$ ，那么 $(x, y, z)$ 的 $p_i$ 的指数只能为 $k_L$ ，如果 $k_L\neq k_G$ ，那么 $(x, y, z)$ 中必有一个数 $p_i$ 的指数为 $k_L$ ，一个为 $k_G$ ，一个满足 $k_G\le k\le k_L$ ，这样的三元组一共有 $6(k_L-k_G)$ 种；

这里做了一个小改动：直接分解 $L/G$

~~本来还打了素数表，不知道为什么WA了~~

inline void factor() {
    memset(g, 0, sizeof(g));
    memset(l, 0, sizeof(l));
    if (L % G) {
        printf("0\n");
        return;
    }
    ll ans = 1;
    L /= G;
    for (register int i = 2; L > 1; ++i) {
        int cnt = 0;
        while (L % i == 0 && L > 1) {
            L /= i;
            cnt++;
        }
        if (cnt) ans *= 6 * cnt;
    }
    printf("%d\n", ans);
}

扩展欧几里得

求解形如 $ax+by=c,a,b,c\in Z,c=k\gcd(a,b)$ 的不定方程。

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

该算法解出了 $ax+by=(a,b)$ 的一组解 $(x_0,y_0)$ ，其通解表示为 $(x_0-k\frac{b}{(a,b)},y_0+k\frac{a}{(a,b)})$ 。

例题 [NOIP2012]同余方程

模板题

例题青蛙的约会

设相遇时间为 $t$ ，那么，两只青蛙相遇可以表示为 $x+mt\equiv y+nt(\bmod l)$ ，即 $x+mt-y-nt=kl$ ，化简得 $(m-n)t+lk=y-x$ 。
扩欧解即可。

例题 [NOI2002]荒岛野人

转化成
$\forall i, j,\quad C_i+t*P_i\equiv C_j+t*P_j(\bmod m),t\le min(L_i,L_j)$

枚举 $m$ 即可。

注意要从最大洞穴编号开始枚举。~~就这个我WA了3次。~~

7.同余

定义7.1： $a\equiv b(\bmod m) \iff a\bmod m=b\bmod m$
$\iff a - b = mk \iff m\mid a-b$ .

同余的性质

$a\equiv a$
$a\equiv b \iff b\equiv a$
$a\equiv b,b\equiv c \Rightarrow a\equiv c$
$a\equiv b,c\equiv d\Rightarrow a\pm c\equiv b\pm d$
$a\equiv b,c\equiv d\Rightarrow ac\equiv bd$

逆元

定义7.2：若 $(a,m)=1,ab\equiv 1\bmod m$ 则称 $b$ 为 $a$ 的逆元

扩欧解 $ab + km = 1$ 即可。

也可以用费马小定理求。

可以在 $O(n)$ 的时间内处理 $1\sim n$ 的逆元：

考虑以下式子：

$1^{-1}\equiv 1 (\bmod p)$

设 $p=ax + r\equiv 0(\bmod p)$

$ar^{-1}+x^{-1}\equiv 0(\bmod p)$

$x^{-1} \equiv -ar^{-1}(\bmod p)$

即 $x^{-1}\equiv -\lfloor \displaystyle\frac{p}{x}\rfloor\cdot(p\bmod x)^{-1}\ \ \ (\bmod p)$

这样就可以O(1)递推了

inv[1] = 1;
for(int i = 2; i <= n; ++i) {
    inv[i] = ((-inv[P % i] * (P / i) ) %P+P)% P;
}

费马小定理

定理7.3： $p$ 是质数， $(a,p)=1\Rightarrow a^{p-1}\equiv1(\bmod p)$

费马小定理没有逆定理

素数测试

虽然费马小定理没有逆定理，但是费马小定理的逆否命题是正确的，所以我们可以用费马小定理来验证一个数是否是合数，这样，多次选取a的值，就能大致确定一个数是否是质数。

可惜总有一些数是特殊的，能卡掉这种算法。

所以我们就要使用Miller-Rabin算法

定理7.4： $x^2\equiv 1(\bmod p) \Rightarrow x\equiv \pm 1(\bmod p)$ （二次探测定理）

对于一个可能是质数的数，如果它是质数，那么，其必然满足：

$\forall a\ne kp,a^{p-1}\equiv 1$

而由于二次探测定理，就有

$a^{(p-1)/2}\equiv \pm1(\bmod p)$

如果余 $+1$ ，则可以递归下去检验，如果余 $-1$ ，那么停止递归，我们就认为 $p$ 是一个可能的素数。

多次测试，避免偶然性。

实践中多自下而上操作。

考虑构造一个数 $t$ ，满足 $p-1=t\times 2^i$ 且 $t$ 最小。

那么，由二次探测定理，必然有 $a^t\equiv 1$ 或 $(a^{t})^{2^k} \equiv -1$ .

bool Miller-Rabin(int p, int T) {
    if (p == 2) return true;
    if (p < 2) return false;
    int t = p-1, x = 0;
    while (!(t&1)) {
        t >>= 1;
        x++;
    }
    while (T--) {
        int a = rand() % (p-1) + 1;
        if(pow_mod(a, t, p) == 1) continue;
        flag = 0;
        for (int i = 1; i <= x; ++i) {
            if (pow_mod(a, (t<<i), p) == p-1) {
                flag = 1;
                break;
            }
        }
        if (!flag) return false;
    }
    return true;
}

中国剩余定理

定理7.5：中国剩余定理.

对于模线性方程组：

$x\equiv a_1(\bmod m_1)$

$x\equiv a_2(\bmod m_2)$

$\cdots$

$x\equiv a_n(\bmod m_n)$

当 $(m_1, m_2,\cdots,m_n) = 1$ 时有唯一解，

$x = (\sum\limits^{n}_{i=1}a_it_iM_i)\bmod M,$ $(M=m_1m_2\cdots m_n,M_i=M/a_i,t_iM_i\equiv 1(\bmod a_i)$

8.整除分块

例题：求 $\sum\limits_{i}^{n}\lfloor\displaystyle\frac{n}{i}\rfloor$

方法一： $O(n)$ 枚举，naive！

方法二：整除分块

int ans = 0, n = 100;
for (int i = 1, j; i <= n; i = j + 1) {
    j = min(n, (n/(n/i)));//右端点，玄学操作
    ans += (n/i)*(j-i+1);
}
printf("%d\n", ans);

例题：求 $\sum\limits_{i}^{n}k\bmod i$

转化成 $n*k-\sum^n_ii\lfloor\frac{k}{i}\rfloor$ ,
整除分块，注意到商相同时，后面的求和部分成等差数列，做即可。

ll ans = n * k;
for (ll i = 1, j; i <= n; i = j + 1) {
    if(k / i) j = min(n, (k/(k/i)));
    else j = n;
    ans -= (j-i+1)*(i+j)*(k/i)/2;
}
printf("%lld\n", ans);

例题：[清华集训2012]模积和

题解

9.数论函数

定义域为整数的函数

$\sigma(x)=\sum_{d\mid x}d$
$d(x)=\sum_d [d\mid x]$
$id(x)=x$
$e(x)=[x==1]$
$1(x)=1$
积性函数：对于 $(m, n)=1$ ，有 $f(mn) = f(m)f(n)$

欧拉函数 $\varphi$

$\varphi(x)=\sum^x_d [(x,d)=1]$

基于以下三条定理，我们可以线性的求出欧拉函数表

$\mbox{9.1:}\quad\mbox{if}\;p\;\mbox{is prime}\;\mbox{then}\; \varphi(p)=p-1.$
$\mbox{9.2:}\quad\mbox{if}\;i\bmod p=0\;\mbox{then}\; \varphi(ip)=p\cdot\varphi(i).$
$\mbox{9.3:}\quad\mbox{if}\;(m, n)=1\;\mbox{then}\; \varphi(mn)=\varphi(m)\varphi(n).$
定理1易证，定理3是欧拉函数的性质，下面给出定理2的证明：
$引理：$
$\mbox{引理9.2.1：}\quad\mbox{if}\;(a,b)\ne1\;\mbox{then}\;(a+b,b)\ne1.$
$证明：$
$\mbox{证明：} \quad\mbox{let}\;d=(a,b)\;\mbox{then}\;a=k_ad,b=k_bd\\\mbox{Therefore},a+b=(k_a+k_b)d\;\mbox{then}\;(a+b,b)\ne1.$
$引理：$
$\mbox{引理9.2.2：}\quad\mbox{if}\;(a,b)=1\;\mbox{then}\;(a+b,b)=1.$
$证明：$
$\mbox{证明：} \quad\mbox{if}\;(a+b,b)\ne1\;\mbox{let}\;d=(a+b,b)\;\\\mbox{then}\;a+b=k_1d,b=k_2d\\\mbox{Therefore},a=(k_1-k_2)d\;\mbox{then}\;(a,b)\ne1.\\\mbox{Therefore}\quad (a+b,b)=1.$
$定理证明引理这样的有个而由引理，其他的数都与互质考虑中与不互质的数的个数$
$\mbox{定理9.2证明:}\quad\forall a<i,(a,i)\ne1\Rightarrow (a+ki,ip)\ne1,(0\le k<p)(引理1)\\这样的a+ki有p\varphi(i)个,而由引理2，其他的数都与ip互质\\考虑[1,ip]中与ip不互质的数的个数ip-\varphi(ip)=ip-\varphi(i)p\\\Longrightarrow \varphi(ip)=p\varphi(i)$

notp[1] = phi[1] = 1;
for (int i = 2; i <= n; i ++) {
    if (!notp[i]) pri[++ psz] = i, phi[i] = i - 1;
    for (int j = 1; j <= psz; j ++) {
        int k = i * pri[j];
        if (k > n) break ;
        notp[k] = 1;
        if (i % pri[j] == 0) {
            phi[k] = phi[i] * pri[j]; //mark
            break;
        } else {
            phi[k] = phi[i] * phi[pri[j]];
        }
    }
}

定理9.4： $a^{\varphi(n)}\equiv1(\bmod n)$ （欧拉定理）

莫比乌斯函数 $\mu$

$\mu(x)=\begin{cases}1,\quad x=1\\(-1)^k,\quad x=p_1p_2\cdots p_k,\forall i, j,p_i\ne p_j,\;p_i,p_j\;\mbox{is prime}\\0,\quad\mbox{otherwise}\end{cases}$

可知当 $x$ 有质因子时平方因子时 $\mu(x)=0$ .

莫比乌斯函数可以线性筛

notp[1] = phi[1] = mu[1] = 1;
for (int i = 2; i <= n; i ++) {
    if (!notp[i]) pri[++ psz] = i, phi[i] = i - 1, mu[i] = -1;
    for (int j = 1; j <= psz; j ++) {
        int k = i * pri[j];
        if (k > n) break ;
        notp[k] = 1;
        if (i % pri[j] == 0) {
            mu[k] = 0;//有平方因子
            break ;
        } else {
            mu[k] = -mu[i];//无平方因子，多了一个素因子
        }
    }
}

定理9.5： $\sum_{d\mid n}\mu(d)=[n=1]$ .

10.反演

懵逼五四繁衍莫比乌斯反演

理解方式1

有如下两条定理：

定理10.1： $F(n)=\sum_{d\mid n}f(d) \iff f(n)=\sum_{d\mid n}\mu(d)F(\displaystyle\frac{n}{d})$
定理10.2： $F(n)=\sum_{n\mid d}f(d) \iff f(n)=\sum_{n\mid d}\mu(\displaystyle\frac{d}{n})F(d)$

理解方式2

定义10.3：狄利克雷卷积:
$(f*g)(x)=f(x)*g(x),\\(f\times g)(x)=\sum_{d\mid x}f(d)g(\displaystyle\frac{x}{d})$
伪公理10.4： $f=f\times e$
伪公理10.5： $id=\varphi \times 1$
伪公理10.6： $e=\mu\times1$
$F=f\times1\\F\times\mu=f\times1\times\mu=f\times e=f$

重要结论

$d(ij) = \sum_{x|i}\sum_{y|j}e(\gcd(i,j))$

例题们

最最基础的：
$\sum^n_{i=1}e(gcd(i,n))$

解：

$=\sum^n_{i=1}\color{Red}{(\mu\times 1)}(gcd(i,n))\quad(10.6)\\ =\sum^n_{i=1}\color{Red}{\sum_{d\mid gcd(i,n)}\mu(d)}\quad(10.3)\\ =\sum^n_{i=1}\sum_\color{Red}{d\mid i \& d\mid n}\mu(d) \\ =\color{Red}{\sum_{d\mid n}\sum^n_{i=kd}}\mu(d) \quad( \mbox{interchanging the order of summation})\\ =\sum_{d\mid n}\mu(d)\color{Red}{(\frac{n}{d})}\\ =\mu\times id \quad(\mbox{10.3 beautiful but useless})$

最基础的：
$\sum_i^n\gcd(i,n)$

解：

$=\sum_i^n\color{Red}{id}(\gcd(i,n))\\ =\sum_i^n\color{Red}{\varphi\times1}(\gcd(i,n))\quad(10.5)\\ =\sum_i^n\color{Red}{\sum_{d\mid \gcd(i,n)}\varphi(d)}\quad(10.3)\\ =\color{Red}{\sum_{d\mid n}\sum^n_{i=kd}}\varphi(d) \quad( \mbox{interchanging the order of summation})\\ =\sum_{d\mid n}\varphi(d)\color{Red}{(\frac{n}{d})}$

以上两个反演十分基础，必须全面理解。

还是很基础的：
$\sum_{i=1}^N\sum_{j=1}^M\gcd(i,j)$

解：

$=\sum_{i=1}^N\sum_{j=1}^M\sum_{d\mid\gcd(i,j)}\varphi(d)\\ =\sum_d\sum_{d\mid i}\sum_{d\mid j}\varphi(d)\\ =\sum_d\lfloor\frac{N}{d}\rfloor\lfloor\frac{M}{d}\rfloor\varphi(d)\\$

概率与期望

代数

1.排列和逆序对

定义1.1排列： $1\sim n$ 的数组成的排列（不重）。
定义1.2逆序对： $i<j,a_i>a_j$ .
定义1.3对换：交换一个排列中的两个数。
定义1.4奇\偶排列：按逆序对的数目。
定理1.5：对换改变排列的奇偶性。
定理1.6：在全部 $n(n \ge 2)$ 阶排列中，奇偶排列各占一半
定理1.7：任意一个排列可经过一系列对换变成自然排列，并且所做对换次数的奇偶性与这个排列的奇偶性相同。

2.行列式

a[n][n],y[n];
do {
    res = 1;
    for (int i = 1; i <= n; ++i) 
        res *= a[i][y[i]];
    if(isOdd(y)) res = -res;
    ans += res;
} while (next_permuation(y+1, y+n+1))

引理2.1：行列互换，值不变。
引理2.2：用一个数乘行列式的某行等价于行列式的值乘这个数。
引理2.3：可以把一行的值拆成两部分，从而拆开行列式，从而形成两个行列式，其和等于原行列式。
引理2.4：对换行列式中两行的位置，行列式反号。
引理2.5：如果行列式中有两行成比例，则行列式的值为0.
引理2.6：把一行的某个倍数加到另一行，行列式的值不变。

余子式

定义：行列式去掉某一行和某一列。( $M_{ij}$ )
代数余子式： $T_{ij}=|M_{ij}|\times (-1)^{(i+j)}$

$|D|=\sum\limits^n_{i=1} D_{1i}\cdot T_{1i}$

Cramer法则

线性方程组的系数行列式 $D\ne 0$ 时有唯一解 $x_j=D_j/D$ 。
其中 $D_j$ 为将 $D$ 中的第 $j$ 列换成等号右边的数的行列式。

高斯消元法

3.矩阵

$n$ 个点的完全图生成树的个数为 $n^{n-2}$