该笔记是在大二时学习离散数学这门课程时做的，同时也看了其他有关的书，并用C++来验证这些定理。😄

素数-合数

设$a,b$是两个整数，且$b\ne 0$。如果存在整数 $c$ 使得 $a=bc$，则称 $a$ 被 $b$ 整除 或者 $b$ 整除 $a$，记作 $b\mid a$ ，不整除记作 $b\nmid a$

任何正整数都有两个正因子：1和它本身，称作它的平凡因子，除了平凡因子外的因子称作 真因子。

• 如果正整数 $a$ 大于 1 且只能被1和它本身自己整除，则称 $a$ 为素数或质数；如果 $a$ 大于1且不是素数，则 $a$ 为合数。

• $a>1$ 是合数当且仅当 $a=bc$，其中 $1<b<a,1<c<a$。

算术基本定理

设 $a>1$，则

$a=p_1^{r_1}\times p_2^{r_2}\times p_3^{r_3}\times ... \times p_k^{r_k}$

其中 $p_1,p_2,...,p_k$ 是不同的素数，$r_1,r_2,...r_k$ 是正整数。定理中的表达式称作整数$a$ 的 素因子分解。比如

$30=2\times 3\times 5\\ 88=2^3\times 11\\ 99099=3^2\times 7\times 11^2\times 13\\ 1024=2^{10}$

若所有的$r_i=0$，则 $a=1$。显然，$a$的素因子只能含有 $a$ 中的素因子，即有下面推论：

推论：设 $a=p_1^{r_1}\times p_2^{r_2}\times p_3^{r_3}\times ... \times p_k^{r_k}$ ，其中 $p_1,p_2,...,p_k$ 是不同的素数，$r_1,r_2,...r_k$ 是正整数。

则正整数 $d$ 为 $a$ 的 因子 的充要条件是 $d=p_1^{s_1}\times p_2^{s_2}\times ...\times p_k^{s_k}$。其中 $0\le s_i\le r_i,i=1,2,...,k$

例子：$99099$ 有多少个正因子？

解：由于 $99099=3^2\times 7\times 11^2\times 13$，有推论可知， $d=3^{s_1}\times 7^{s_2}\times 11^{s_3}\times 13^{s_4}$

$s_1\in [0,2],s_2\in [0,1],s_3\in [0,2],s_4\in [0,1]$，因此 $99099$ 的正因子个数为 $3\times 2\times 3\times 2=36$（排列组合）

素数定理

$\lim_{n\to +\infty} \frac{\pi(n)}{n/\ln n}=1$

检查一个正整数是否为素数称作 素数测试。

• 如果 $a$ 是一个合数，则 $a$ 必有一个 小于等于 $\sqrt a$ 的 真因子

  推论：如果 $a$ 是一个合数，则 $a$ 必有一个 小于等于 $\sqrt a$ 的 素因子

• 埃拉托斯特尼（Eratosthene）素数筛选法

  要求某一个正整数 $a$ 在一定范围内的所有素数，从某个素数 $b_1$ 开始，从头到尾删去 $b$ 能够整除 $a$ 的所有正整数，接着在从第二个素数 $b_2$ 开始重复上面的步骤，直到在 $a$ 的范围内只剩下素数。

typedef unsigned long long ull;
const ull XX = 1e9;
bool del[XX + 1];
void eratosthene(ull NUM) {
    // 注意 最终要遍历到 NUM
    for (ull n = 2; n <= NUM; n++)
        // 表示还没有被标记删除
        if (!del[n]) // 删去 n 的 [整数倍] 的其他数字
            // 注意这里一开始就是 i=n*n,目的是保留最初了 单位质数n
            for (ull i = n * n; i <= NUM; i += n)// 打表标记删除
                del[i] = true;
}
int main() {
    ull n = 1000000000;
    eratosthene(n);
    for (int i = 2; i <= n; i++) if (!del[i]) cout << i << " ";
}

当 $n$ 是合数时， $2^n-1$一定是合数

当 $p$ 是素数时，称 $2^p-1$ 的数为 梅森素数。

线性筛

复杂度为 $O(n)$

#include<iostream>
#include<string.h>
using namespace std;

const int M=100001;
int prime[M],isprime[M];

int n,cnt;
void fastprime(){
    memset(isprime,1,sizeof(isprime));
    isprime[1]=0;
    for(int i=2;i<=n;i++){
        if(isprime[i]) prime[cnt++]=i;
        for(int j=0;j<=cnt && i*prime[j]<=n;j++){
            isprime[i*prime[j]]=0;
            if(i%prime[j]==0)break;
        }
    }
}

int main(){
    cin>>n;
    fastprime();
    for(int i=0;i<cnt;i++)
        cout<<prime[i]<<" ";
    cout<<endl;
    return 0;
}

自然数分解为素数的乘积

#include<iostream>
#include<string.h>
using namespace std;

const int M=100001;
int prime[M],isprime[M];

int n,cnt;
void fastprime(){
    memset(isprime,1,sizeof(isprime));
    isprime[1]=0;
    for(int i=2;i<=n;i++){
        if(isprime[i]) prime[cnt++]=i;
        for(int j=0;j<=cnt && i*prime[j]<=n;j++){
            isprime[i*prime[j]]=0;
            if(i%prime[j]==0)break;
        }
    }
}
int main(){ 
    cin>>n;
    fastprime();
    for(int i=0;i<cnt;i++){
        while(n%prime[i]==0){
            cout<<prime[i]<<" ";
            n/=prime[i];
        } 
    }
    cout<<endl;
    return 0;
}

同余

a与b模m同余 $a\equiv b(\mod m)$，即： $a \mod m=b \mod m $

同余关系是等价关系

• 自反性. $a\equiv (a\mod m)$
• 传递性. $a\equiv b(\mod m),b\equiv c(\mod m)\Rightarrow a\equiv c(\mod m)$
• 对称性. $a\equiv b(\mod m)\Rightarrow b\equiv a(\mod m)$

模算术运算。$a\equiv b(\mod m)$，$c\equiv d(\mod m)$，则

$a\pm c\equiv b\pm d(\mod m)\\ a\times c\equiv b\times d(\mod m)\\ a^k\equiv b^k(\mod m)\\$

设 $c,m$ 互为素数，则 $a\equiv b(\mod m) \Leftrightarrow c\times a\equiv c\times b(\mod m)$

欧拉定理和费马小定理

欧拉定理：设 $a$ 和 $n$ 互为素数，则 $a^{f(n)}\equiv 1(\mod n)$

当 $p$ 为素数时，$f(n)=p-1$，于是得到费马小定理

设 $p$ 是素数，$a$ 与 $p$ 互素，则 $a^{p-1}\equiv 1(\mod p)$ 或者另外一种形式 $a^p\equiv a(\mod p)$

利用费马小定理，可以在不用因子分解的情况下就可以判断一个数是否为 合数。比如 $9$，取 $a=2$，计算 $2^{9-1}\equiv 4(\mod 9)$，对比费马小定理可知 9 是合数。

产生均匀伪随机数–线性同余法LCG

这种产生的随机数属于 统计学伪随机数生成器

产生伪随机数递推公式：

$x_n=(a\times x_{n-1}+c)\mod m ,n=1,2,...$

其中 $x_0$ 为初始时的种子数，若 $c=0$，上述递推式成为 乘同余数。此时取 $m=2^{31}-1,a=7^5,c=0$ 的乘同余法是最常用的均匀伪随机数发生器。$a$ 还可以取其他数值 48271

#include<bits/stdc++.h>
using namespace std;
size_t __SEED=1;
void my_srand(size_t S){ __SEED=S; }
size_t my_rand(){
    // m = (1<<31)-1	a = 7^5
    int m=0x7fffffff,c=0,a=16807;
    __SEED=(a*__SEED+c) % m;
    return __SEED;
}
int main() {
    my_srand(time(NULL));
    for(int i=0;i<10;i++) cout<<my_rand()<<endl;
}

快速幂

二分思想–递归法

求 $f(a,b)=a^b$，递归式如下：

$a^b=f(a,b)= \begin{cases} 1&,b=0\\ a\times f(a,b-1)&,b为奇数\\ f(a^{\frac{b}{2}},\frac{b}{2})\times f(a^{\frac{b}{2}},\frac{b}{2})&,b为偶数\\ \end{cases}$

using ll=long double;
ll quick_pow(int a,int b){
    if(b==0)return 1;
    if(b&1)return a*quick_pow(a,b-1);
    ll m=quick_pow(a,b/2);
    return m*m;
}

二进制位分解–迭代法

$a^b$，$b$ 的二进制位（取其中有效的位: 1） 。指数的变化位 $... 64\quad 32\quad 16\quad 8\quad 4\quad 2\quad 1$，每次翻倍

如 $b=13=(1101)_2=2^3+2^2+2^0=8+4+1$

$a^{13}=a^{8+4+1}=a^{2^3+2^2+2^0}=a^8\times a^4\times a^1$

using ll=long double;
ll quick_pow(ll a,int b){
    ll ans=1;
    while(b){ // 直到b=0
        if(b&1) ans=ans*a; // 有效位1
        a=a*a;				// 指数 b=2*i
        b>>=1;				// b右移取有效位1
    }
    return ans;
}

快速幂-取模运算

#include <cstdio>
#include <cstdlib>
int b, p, k;
typedef unsigned long long ll; 
unsigned long long qm() {
    if (p == 0) return 1 % k;
    ll ans = 1, bb = b, pp = p;
    bb %= k;
    while (pp) {
        if (pp & 1) ans = (ans * bb) % k;
        bb = (bb * bb) % k;
        pp >>= 1;
    }
    return ans;
}
int main() {
    scanf("%d%d%d", &b, &p, &k);
    unsigned long long ans = qm();
    printf("%d^%d mod %d=%ld\n", b, p, k, ans);
    return 0;
}

欧拉函数

欧拉函数（Euler’s totient function），即 $\phi(x)$ ，表示的是 小于等于 $n$ 和 $n$ 互质(公约数只有1) 的数的个数。

$\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})\cdots (1-\frac{1}{p_k})$

也可以写成

$\phi(n)=n\frac{p_1-1}{p_1}\frac{p_2-1}{p_2}\cdots\frac{p_k-1}{p_k}$

其中 $p_1,p_2,p_k$ 为分解出来的不同的 质因数。

• $\phi(1)=1$

• 当 $n$ 是 质数 的时候，显然有 $\phi(n)=n-1$ （也就是除了 $n$ 本身）

• 欧拉函数的递推公式： 令 $p$ 是 $n$ 的最小质因数，如果 $p^2$ 能整除 $n$ ，那么 $\phi(n)=\Phi(\frac{n}{p})(p-1)$

求某个数的欧拉函数值如下，复杂度为 $O(\sqrt{n})$

#include<iostream>
#include<cmath>
using namespace std;
int phi(int n){
    int ans=n;
    int cnt=sqrt(n+0.5)+1;
    for(int i=2;i<cnt;i++){
        if(n%i==0){
            // // 由 ans=ans* (i-1) / i 化简
            ans-=ans/i; 
            while(n%i==0)n/=i;
        }
        if(n==1)break;
    }
    if(n>1)ans-=ans/n;
    return ans;

}

int main(){
    int n;
    cin>>n;
    cout<<phi(n)<<endl;
    return 0;
}

线性筛求欧拉函数表

复杂度为 $O(n)$

#include<iostream>
#include<cstring> 
using namespace std;

const int N=100001;
bool isprime[N];
int prime[N];
int phi[N];
int cnt;
void fastphi(int n){
    memset(isprime,1,sizeof(isprime));
    isprime[0]=isprime[1]=0;
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(isprime[i]) {
            prime[cnt++]=i;
            phi[i]=i-1; 
        }
        // prime[j] 为最小质因数
        for(int j=0;j<=cnt && i*prime[j]<=n;j++){
            isprime[i*prime[j]]=0;
            if(i%prime[j]==0) {
				// 欧拉函数递推式
                phi[i*prime[j]]=phi[i] * prime[j];
                break;
            }
            // 欧拉函数递推式
            phi[i*prime[j]]=phi[i] * (prime[j]-1);
        }
    }
}


int main(){
    int n;
    cin>>n;
    fastphi(n);
    for(int i=0;i<cnt;i++)
        cout<<phi[i]<<" ";
    cout<<endl;
    return 0;
}

霍纳规则

适用范围：多项式求值问题

简介：假设有 $n＋2$ 个实数 $a_0,a_1,...,a_n$ 和 $x$ 的序列，要对多项式 $P_n(x)= a_nx_n+a_{n-1}x_{n-1}+...+a_1x+a_0$ 求值，直接方法是对每一项分别求值，并把每一项求的值累加起来，这种方法十分低效，它需要进行 $n+(n-1)+...+1=n(n+1)/2$ 次乘法运算和 $n$ 次加法运算。有没有更高效的算法呢?答案是肯定的。

通过如下变换我们可以得到一种非常快的算法，即 $P_n(x)= a_nx_n+a_{n-1}x_{n-1}+...+a_1x+a_0=((...(((a_nx +a_{n-1})x+a_{n-2})x+ a_{n-3})...)x+a1)x+a0$，这种求值的安排我们称为 霍纳法则。

C++ code

#include<iostream>
using namespace std;

double horner_rule(double *A,int n,double x){
    double ans=0;
    // 从 n 开始
    for(int i=n-1;i>=0;i--){
        ans=ans*x+A[i];
    }
    return ans;
}

int main(){
    double A[]={1,2,3,4};
    double x=2;
    cout<<horner_rule(A,sizeof(A)/sizeof(A[0]),x)<<endl;
    return 0;
}
// 49

排列组合

$(1)\ P(n,r) = \frac{n!}{(n-r)!}.n\ge r\\ (2)\ C(n,r) = \frac{n!}{r!*(n-r)!}.n\ge r\\$

推论： 设 $n,r$ 为正整数，则

$C(n,r)=\frac{n}{r}C(n-1,r-1)\\ C(n,r)=C(n,n-r)\\ C(n,r)=C(n-1,n-r)+C(n-1,r)$

例1：从 $S=\{1,2,...,n\}$ 中选择$k$个不相邻的数，有多少种方法？

$C(n-(k-1),k)=C(n-k+1,k)$

图论

握手定理

• 在任何图中，所有顶点的度数之和等于边数的2倍

$\sum_{v\in V}deg(v)=2|E|$

• 在任何有向图中，所有顶点的 入度 之和等于所有顶点的 出度 之和，等于边数 $|E|$。

平面图

• 一个有限平面图中，面的次数之和等于边数的两倍。

• 设 $G$ 是连通的平面图，且每条边的次数至少为 $k(k\ge 3)$，则平面图的边数 $e$ 和顶点数 $v$ 关系 ：$e\le \frac{k}{k-2}\times(v-2)$

• 设 $G$ 是 $v(v\ge 3)$ 阶 $e$ 条边的简单平面图，则：$e\le3v-6$

无向树-树

• 树：$边数=顶点数-1\Leftrightarrow e=n-1$

• 设 $G$ 为 $n$ 阶 $m$条边的无向连通图，则 $m\ge n-1$

• 设有完全 $m$ 叉树，其树叶数为 $t$，分支点数（内点+树根）为 $i$ ，则 $(m-1)\times i=t-1$

  • 证明：$m*i=(t+i)-1$

• 设 $G$ 是有 $n$ 个结点，$m$ 条边的连通图，必须删去 $G$ 的 $m-n+1$ 条边，才能确定 $G$ 的一棵 生成树。

最小的生成树

为了造出一棵最小生成树，我们从最小边权的边开始，按边权从小到大依次加入，如果某次加边产生了环，就扔掉这条边，直到加入了 $n-1$ 条边，即形成了一棵树。

最小生成树一定是含有 $n$ 个顶点和 $n-1$ 条边。
所以可以得到一个推论：
$n-1$ 条边 <=> $1$ 棵最小生成树
$n-2$ 条边 <=> $2$ 棵最小生成树（将 $n-1$ 分为 $n-1$ 和$1$ 条边）
$n-3$ 条边 <=> $3$ 棵最小生成树
$\vdots$
$n-k$ 条边 <=> $k$ 棵最小生成树。其实可以这么理解：从 n-1 条边得到了一颗最小生成树之后，根据 树 的定义，我们知道，若从一颗最小生成树中删除 $i$ 条边后，会形成多个树，也就是森林；而且每一个子树也是最小生成子树。

注意： 一个顶点也可与作为一颗最小生成树。比如洛谷有一题 p1195

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

#define INF 0x7fffffff
#define N 100001

int n, m, k, cnt, ans;
int f[N];
struct edge {
    int u, v, w;
};
vector<edge> E;

struct cmp {
    bool operator()(edge e1, edge e2) { return e1.w < e2.w; }
};

int find(int x) {
    if (f[x] == x) return x;
    return f[x] = find(f[x]);
}

int find2(int x) {
    while (f[x] != x) {
        f[x] = f[f[x]];
        x = f[x];
    }
    return f[x];
}

// n-k 条边得到 k 个最小生成树
// 因此 kruskal算法只能选取 n-k 条[最小成本]的边来将这些边组成 k 个最小生成树
void kruskal() {
    for (int i = 0; i < E.size(); i++) {
        edge e = E[i];
        int f1 = find2(e.u);
        int f2 = find2(e.v);
        if (f1 == f2) continue;
        f[f1] = f2;
        ans += E[i].w;  // 计算k棵mst的成本
        cnt++;          // 统计边数
        if (cnt >= n - k) break;
    }
    if (cnt == n - k)
        cout << ans;
    else
        cout << "No Answer";
}
// 一个顶点也可与作为一颗最小生成树
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    int u, v, w;
    for (int i = 1; i <= n; i++) f[i] = i;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        E.push_back(edge{u, v, w});
    }
    sort(E.begin(), E.end(), cmp());
    kruskal();
    return 0;
}