首页 书籍 挑战程序设计竞赛

#

# 数据结构

# 优先队列和堆

优先队列（Priority Queue）是一种特殊的队列，它的特点是每次出队的元素是队列中优先级最高的元素。在优先队列中，元素通常带有优先级，这样在出队时会优先选择优先级最高的元素。优先队列常常用于实现任务调度、事件模拟等场景。

在 C++ 中，STL（Standard Template Library）提供了优先队列的实现，可以使用 <queue> 头文件中的 priority_queue 类来创建优先队列。通过指定比较函数或使用默认的比较函数，可以实现不同类型的优先队列（最大堆或最小堆）。

#include <iostream>
#include <queue>
using namespace std;
int main() {
    // 创建一个最大堆的优先队列
    priority_queue<int> maxHeap;
    // 插入元素
    maxHeap.push(3);
    maxHeap.push(5);
    maxHeap.push(1);
    // 访问队首元素
    cout << maxHeap.top() << endl;
    // 弹出队首元素
    maxHeap.pop();
    cout << maxHeap.top() << endl;
    return 0;
}
堆（Heap）是一种特殊的树形数据结构，常用于实现优先队列。堆分为最大堆和最小堆两种类型，最大堆指父节点的值大于或等于任意一个子节点的值，最小堆则相反，父节点的值小于或等于任意一个子节点的值。


在实际应用中，通常使用二叉堆（Binary Heap）来实现堆。二叉堆是一种完全二叉树，可以使用数组来表示。在数组中，根节点存储在索引 1 处，父节点和子节点之间的关系可以通过索引之间的计算得到。这种表示方法使得插入和删除元素时能够快速调整堆的结构。


实现：最小堆。插入：直接插到数组末尾，然后上浮；删除，最小值删除（头部），并把数组末尾的元素放到开头并删除，然后下沉


    

  • 对于节点 i，它的左子节点索引为 2i，右子节点索引为 2i+1
    • 

  • 对于节点 i，它的父节点索引为 i/2
    • 



#include <iostream>
#include <vector>
using namespace std;
// 最小堆类
class MinHeap {
private:
    vector<int> heap; // 使用 vector 存储堆元素
    // 上浮操作，用于插入元素时维护堆的性质
    void swim(int k) {
        while (k > 1 && heap[k/2] > heap[k]) { // 如果当前节点的值小于其父节点的值，则交换它们
            swap(heap[k/2], heap[k]);
            k = k/2; // 更新节点索引
        }
    }
    // 下沉操作，用于提取最小值时维护堆的性质
    void sink(int k) {
        int N = heap.size() - 1; // 堆的大小
        while (2*k <= N) { // 当存在子节点时进行循环
            int j = 2*k;
            if (j < N && heap[j] > heap[j+1]) j++; // 找到较小的子节点
            if (heap[k] <= heap[j]) break; // 如果当前节点的值小于等于最小的子节点的值，则不需要调整
            swap(heap[k], heap[j]); // 否则交换当前节点和最小子节点
            k = j; // 更新节点索引
        }
    }
public:
    MinHeap() {
        heap.push_back(-1); // 占位符，不使用索引 0
    }
    // 插入元素
    void insert(int x) {
        heap.push_back(x); // 将元素添加到末尾
        swim(heap.size() - 1); // 上浮操作
    }
    // 提取最小值
    int extractMin() {
        int minVal = heap[1]; // 最小值即为堆顶元素
        swap(heap[1], heap.back()); // 将堆顶元素与末尾元素交换
        heap.pop_back(); // 删除末尾元素
        sink(1); // 下沉操作
        return minVal; // 返回最小值
    }
    // 获取堆的大小
    int size() {
        return heap.size() - 1; // 不算占位符
    }
};
int main() {
    MinHeap minHeap;
    minHeap.insert(3);
    minHeap.insert(1);
    minHeap.insert(5);
    cout << minHeap.extractMin() << endl;
    cout << minHeap.extractMin() << endl;
    return 0;
}
# Expedition




思路：优先序列。将 A 从大到小排序，一次性把油用完，路过的加油站的油放进优先序列里，没油了从优先序列里加最大的油，ans++。如果没到达终点优先序列就没油了则输出 - 1。


#include <iostream>
#include <queue>
#include<algorithm>
using namespace std;
// 比较函数，用于排序加油站信息，按照距离降序排列
bool cmp(pair<int,int> a, pair<int,int> b)
{
    return a.first > b.first;
}
int main()
{
    int n;
    cin >> n; // 读入加油站数量
    pair<int,int> ab[20005]; // 存储加油站信息的数组
    for (int i = 1; i <= n; i++)
    {       
        cin >> ab[i].first >> ab[i].second; // 读入每个加油站的距离和油量
    }
    n++;
    ab[n].first = 0;
    ab[n].second = 0;
    sort(ab + 1, ab + n, cmp); // 按照距离降序排序加油站信息
    int l, p;
    cin >> l >> p; // 读入起点位置和初始油量
    int ans = 0;
    int x = l, oil = p;
    priority_queue<int, vector<int>, less<int>> q; // 优先队列，存储可以到达的加油站的油量
    for (int i = 1; i <= n; i++)
    {
        int d = x - ab[i].first; // 计算当前位置与下一个加油站的距离
        while (oil < d) // 当油量不足以到达下一个加油站时
        {
            if (q.empty()) // 如果优先队列为空，无法加油到达下一个加油站
            {
                cout << -1;
                return 0;
            }
            oil += q.top(); // 加油到达下一个加油站
            q.pop(); 
            ans++; // 加油次数加一
        }
        oil -= d; // 更新油量
        q.push(ab[i].second); // 将当前加油站的油量加入优先队列
        x = ab[i].first; // 更新当前位置为下一个加油站的位置
    }
    cout << ans; // 输出最终加油次数
    return 0;
}
# 二叉搜索树


二叉搜索树（Binary Search Tree，简称 BST）是一种特殊的二叉树，具有以下性质：


    

  1. 对于二叉搜索树中的每个节点，其左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。
    2. 

  2. 二叉搜索树的左子树和右子树也分别是二叉搜索树。
    3. 



由于这些性质，二叉搜索树可以高效地支持如查找、插入、删除等操作，时间复杂度为 O (logn)，其中 n 为二叉搜索树中节点的数量。


插入节点：


    

  1. 从根节点开始，比较要插入节点的值与当前节点的值。
    2. 

  2. 如果要插入节点的值小于当前节点的值，则向左子树移动；如果大于当前节点的值，则向右子树移动。
    3. 

  3. 如果移动到的位置为空，则将新节点插入到这个位置。
    4. 

  4. 如果新节点的值等于当前节点的值，则可以根据具体情况选择是替换还是进行其他操作（这里一般选择不插入相同值的节点）。
    5. 



删除节点：


    

  1. 如果要删除的节点没有子节点，直接删除即可。
    2. 

  2. 如果要删除的节点只有一个子节点，将其父节点指向其子节点即可。
    3. 

  3. 如果要删除的节点有两个子节点，需要找到其右子树中最小的节点（或者左子树中最大的节点）来取代它。

      

    • 找到右子树中最小的节点：即找到右子树的最左节点。
      • 

    • 将该最小节点的值复制到要删除的节点上，并删除最小节点。
      • 

    

    4. 



#include <iostream>
using namespace std;
// 二叉搜索树节点结构
struct Node {
    int key;
    Node* left;
    Node* right;
    // 构造函数
    Node(int k) : key(k), left(nullptr), right(nullptr) {}
};
// 二叉搜索树类
class BinarySearchTree {
private:
    Node* root; // 根节点
    // 插入节点的辅助函数
    Node* insertHelper(Node* root, int key) {
        if (root == nullptr) {
            return new Node(key);
        }
        if (key < root->key) { // 如果要插入节点的值小于当前节点的值
            root->left = insertHelper(root->left, key); // 向左子树移动
        } else if (key > root->key) { // 如果要插入节点的值大于当前节点的值
            root->right = insertHelper(root->right, key); // 向右子树移动
        }
        return root;
    }
    // 查找最小节点
    Node* findMin(Node* node) {
        while (node->left != nullptr) {
            node = node->left;
        }
        return node;
    }
    // 删除节点的辅助函数
    Node* deleteHelper(Node* root, int key) {
        if (root == nullptr) {
            return root;
        }
        if (key < root->key) {
            root->left = deleteHelper(root->left, key);
        } else if (key > root->key) {
            root->right = deleteHelper(root->right, key);
        } else {
            if (root->left == nullptr) {
                Node* temp = root->right;
                delete root;
                return temp;
            } else if (root->right == nullptr) {
                Node* temp = root->left;
                delete root;
                return temp;
            }
            Node* temp = findMin(root->right);
            root->key = temp->key;
            root->right = deleteHelper(root->right, temp->key);
        }
        return root;
    }
    // 查找节点的辅助函数
    bool searchHelper(Node* root, int key) {
        if (root == nullptr) {
            return false;
        }
        if (root->key == key) {
            return true;
        }
        if (key < root->key) {
            return searchHelper(root->left, key);
        } else {
            return searchHelper(root->right, key);
        }
    }
public:
    // 构造函数
    BinarySearchTree() : root(nullptr) {}
    // 插入节点
    void insert(int key) {
        root = insertHelper(root, key);
    }
    // 删除节点
    void remove(int key) {
        root = deleteHelper(root, key);
    }
    // 查找节点
    bool search(int key) {
        return searchHelper(root, key);
    }
};
int main() {
    // 创建二叉搜索树
    BinarySearchTree bst;
    // 插入节点
    bst.insert(5);
    bst.insert(3);
    bst.insert(7);
    bst.insert(2);
    bst.insert(4);
    // 删除节点
    bst.remove(3);
    // 查找节点
    cout << "Is 4 in the tree? " << (bst.search(4) ? "Yes" : "No") << endl;
    cout << "Is 6 in the tree? " << (bst.search(6) ? "Yes" : "No") << endl;
    return 0;
}
C++ 标准库的  set  和  map  实现了二叉搜索树的功能


#include <iostream>
#include <set>
using namespace std;
int main() {
    // 创建一个整数集合
    set<int> s;
    // 插入元素
    s.insert(5);
    s.insert(3);
    s.insert(7);
    s.insert(2);
    s.insert(4);
    // 遍历集合并输出
    cout << "Set elements: ";
    for (auto it = s.begin(); it != s.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    // 查找元素
    int key = 3;
    if (s.find(key) != s.end()) {
        cout << key << " found in the set" << endl;
    } else {
        cout << key << " not found in the set" << endl;
    }
    return 0;
}
#include <iostream>
#include <map>
using namespace std;
int main() {
    // 创建一个整数到字符串的映射
    map<int, string> m;
    // 插入键值对
    m[1] = "one";
    m[2] = "two";
    m[3] = "three";
    // 遍历映射并输出
    cout << "Map elements: ";
    for (auto it = m.begin(); it != m.end(); ++it) {
        cout << "(" << it->first << ", " << it->second << ") ";
    }
    cout << endl;
    // 查找键值对
    int key = 2;
    if (m.find(key) != m.end()) {
        cout << "Key " << key << " found in the map with value " << m[key] << endl;
    } else {
        cout << "Key " << key << " not found in the map" << endl;
    }
    return 0;
}
# 并查集


并查集（Disjoint Set Union，DSU）是一种数据结构，用于管理元素分组和查询元素所属的组别。并查集主要支持两种操作：合并（Union）和查找（Find）。在并查集中，每个集合通常用一棵树表示，树中的一个节点被称为代表元素，代表了该集合。以下是并查集的详细说明：


# 操作：


    

  1. MakeSet(x)：创建一个新的集合，其中包含元素 x。
    2. 

  2. Find(x)：查找元素 x 所属的集合（即根节点的代表元素）。
    3. 

  3. Union(x, y)：将包含元素 x 的集合与包含元素 y 的集合合并成一个集合。
    4. 



# 实现方式：


    

  1. 数组表示：使用一个数组来表示并查集，数组中的每个元素存储该元素所属集合的父节点（或者根节点）。
    2. 

  2. 路径压缩：在进行 Find 操作时，沿着路径将每个节点直接连接到根节点，以减少树的高度，加快后续操作。
    3. 

  3. 按秩合并：在进行 Union 操作时，将秩较小的集合合并到秩较大的集合上，以保持树的平衡，减少树的深度。
    4. 



int par[10005];// 父亲
int rank[10005];// 树的高度
// 初始化 n 个元素
void init(int n) {
    for (int i = 0; i < n; i++) {
        par[i] = i;
        rank[i] = 0;
    }
}
// 查询树的根
int find(int x) {
    if (par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);// 路径压缩，将经过节点的父节点都设为根节点
    }
}
// 合并 x 和 y 所属的集合
void unite(int x, int y) {
    x = find(x);// 找到元素 x 的根节点，路径压缩后 x 变为根节点
    y = find(y);
    if(x == y) return;
    if(rank[x] < rank[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
}
// 判断 x 和 y 是否属于同一个集合
bool same(int x, int y) {
    return find(x) == find(y);
}
# 食物链




动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B， B 吃 C，C 吃 A。

现有 N 个动物，以 1－N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 N 个动物所构成的食物链关系进行描述：

第一种说法是 "1 X Y"，表示 X 和 Y 是同类。

第二种说法是 "2 X Y"，表示 X 吃 Y。

此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1） 当前的话与前面的某些真的话冲突，就是假话；

2） 当前的话中 X 或 Y 比 N 大，就是假话；

3） 当前的话表示 X 吃 X，就是假话。

你的任务是根据给定的 N（1 <= N <= 50,000）和 K 句话（0 <= K <= 100,000），输出假话的总数。


思路：w [fy] = (t - 1 + w [x] + 2 * w [y]) % 3;// 画图总结的公式


#include <iostream>
using namespace std;
int p[50005], w[50005]; // 定义并查集的父节点数组 p 和权值数组 w
// 查找元素 x 所属的集合（根节点）
int find(int x)
{
    int fx = p[x];
    if (x == fx)
        return x;
    // 路径压缩，同时更新权值信息
    p[x] = find(fx);
    w[x] = (w[fx] + w[x]) % 3;
    return p[x];
}
int main()
{
    for (int i = 0; i < 50004; i++)
    {
        p[i] = i;
        w[i] = 0; // 初始化每个元素的父节点和权值信息
    }
    int n, k;
    cin >> n >> k; // 输入元素个数 n 和操作次数 k
    int ans = 0; // 记录不满足条件的操作次数
    while (k--)
    {
        int t, x, y;
        scanf("%d %d %d", &t, &x, &y); // 读入操作类型 t，元素 x 和元素 y
        if (x < 1 || x > n || y < 1 || y > n)
        {
            ans++; // 如果元素 x 或元素 y 不在有效范围内，则答案加一
            continue;
        }
        int fx = find(x);
        int fy = find(y);
        if (fx == fy)
        {
            if (t == 1 && w[x] != w[y])
            {
                ans++; // 如果属于同一集合且不满足条件，答案加一
            }
            else if (t == 2 && (w[x] + 1) % 3 != w[y]) // 3 种关系 a，b 同类，a 吃 b，b 吃 a
            {
                ans++; // 如果属于同一集合且不满足条件，答案加一
            }
        }
        else
        {
            p[fy] = fx; // 合并两个集合
            w[fy] = (t - 1 + w[x] + 2 * w[y]) % 3;// 画图总结的公式
        }
    }
    cout << ans; // 输出最终答案
    return 0;
}
# 图


# 图的搜索




思路：把相邻点染成不同颜色的题叫着色图，对图进行染色需要的最小颜色数称为最小着色数。最小着色数是 2 的图称为二分图。


vector 邻接表的形式如下


顶点：1 2 3 4 5
边的连接关系：
1 2
1 3
2 4
3 4
3 5
4 5



根据上述输入，邻接表会被构建成下面的形式：


G[1]: [2, 3]
G[2]: [1, 4]
G[3]: [1, 4, 5]
G[4]: [2, 3, 5]
G[5]: [3, 4]
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector<int> G[1005]; // 图的邻接表表示
int color[1005]; // 顶点的颜色，0 表示未染色，1 和 -1 分别表示两种颜色
// 深度优先搜索函数，用于染色并检查是否能正确着色
bool dfs(int v, int c)
{
    color[v] = c; // 将顶点 v 染成颜色 c
    for (int i = 0; i < G[v].size(); i++)
    {
        if (color[G[v][i]] == c)
            return false; // 如果相邻顶点颜色相同，则返回 false
        else if (color[G[v][i]] == 0 && !dfs(G[v][i], -c))
            return false; // 如果相邻顶点未染色且染色失败，则返回 false
    }
    return true; // 所有相邻顶点都能正确染色，则返回 true
}
int main()
{
    int n;
    cin >> n; // 读取顶点数量 n
    int x, y;
    while (scanf("%d %d", &x, &y) != EOF) // 从标准输入中读取边的连接关系
    {
        G[x].push_back(y); // 添加边到邻接表中
        G[y].push_back(x); // 无向图需双向添加
    }
    for (int i = 0; i < n; i++)
    {
        if (color[i] == 0) // 若顶点未染色
        {
            if (!dfs(i, 1)) // 进行染色，如果染色失败则输出 "No"
            {
                cout << "No";
                return 0;
            }
        }
    }
    cout << "Yes"; // 所有顶点都能正确染色，则输出 "Yes"
    return 0;
}
# 最短路径问题


# Bellman-Ford


# Dijkstra


# Floyd-Warshall


# 最小生成树


# prim 算法


# Kruskal


# 题目




#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
using namespace std;
const int MAX_N = 5005; // 点的最大数量
const int inf = 1 << 20; // 表示无穷大的值
int dist1[MAX_N]; // 存储最短路径长度
int dist2[MAX_N]; // 存储次短路径长度
struct edge
{
    int to;
    int cost;
};
vector<edge> es[MAX_N]; // 存储边的信息
typedef pair<int, int> P;
priority_queue<P, vector<P>, greater<P>> q; // 优先队列
int main()
{
    int n, r;
    cin >> n >> r; // 输入点的数量和边的数量
    fill(dist1, dist1 + n + 1, inf); // 初始化距离数组为无穷大
    fill(dist2, dist2 + n + 1, inf);
    dist1[1] = 0; // 起始点到自身的距离为 0
    q.push(P(0, 1)); // 将起始点加入优先队列
    for (int i = 0; i < r; i++)
    {
        int x, y, d;
        scanf("%d %d %d", &x, &y, &d); // 输入边的信息
        edge e;
        e.to = x;
        e.cost = d;
        es[y].push_back(e); // 将边信息存入对应的结点中
        e.to = y;
        es[x].push_back(e);
    }
    while (!q.empty())
    {
        P p = q.top();
        q.pop();
        int v = p.second;
        if (dist2[p.second] < p.first)
            continue;
        for (int i = 0; i < es[v].size(); i++)
        {
            edge e = es[v][i];
            int d2 = p.first + e.cost;
            if (dist1[e.to] > d2)
            {
                swap(d2, dist1[e.to]); // 更新最短路径值
                q.push(P(dist1[e.to], e.to));
            }
            if (dist2[e.to] > d2 && dist1[e.to] < d2)
            {
                dist2[e.to] = d2; // 更新次短路径值
                q.push(P(dist2[e.to], e.to));
            }
        }
    }
    cout << dist2[n]; // 输出终点的次短路径长度
    return 0;
}
# 




#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
int par[20005]; // 并查集的父节点数组
int Rank[20005]; // 并查集树的深度数组
struct edge
{
	int from;
	int to;
	int cost; 
};
// 初始化并查集
void init()
{
	for (int i = 0; i < 20005; i++)
	{
		par[i] = i; // 每个节点的父节点初始化为自己
		Rank[i] = 0; // 每个节点的深度初始化为 0
	}
}
// 查找节点所属集合的根节点
int find(int x)
{
	if (x == par[x]) return x;
	else return par[x] = find(par[x]);
}
// 合并两个集合
void unite(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x == y) return;
	if (Rank[x] > Rank[y])
	{
		par[y] = x;		
	}
	else
	{
		par[x] = y;
		if (Rank[x] == Rank[y]) Rank[x]++;
	}
}
// 判断两个节点是否属于同一个集合
bool same(int x, int y)
{
	return find(x) == find(y);
}
// 比较边的权重大小
bool cmp(edge a, edge b)
{
	return a.cost > b.cost;
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		init(); // 初始化并查集
		vector<edge> es; // 存储边的数组
		int n, m, r;
		scanf("%d %d %d", &n, &m, &r); // 输入点的数量、边的数量以及边的权重
		while (r--)
		{
			int x, y, d;
			scanf("%d %d %d", &x, &y, &d); // 输入边的起点、终点和权重
			y += n; // 将终点的索引值加上点的数量，以区分点在不同的集合中
			edge e;
			e.from = x;
			e.to = y;
			e.cost = d;	
			es.push_back(e);					
		}
		sort(es.begin(), es.end(), cmp); // 按边的权重从大到小排序
		int res = 0;
		for (int i = 0; i < es.size(); i++)
		{
			edge e = es[i];
			if (!same(e.from, e.to)) // 如果边的两个端点不在同一个集合中
			{
				unite(e.from, e.to); // 合并这两个集合
				res += e.cost; // 将边的权重加入结果中
			}
		}
		cout << 10000 * (n + m) - res << endl; // 输出最终结果
	} 
	return 0;
}


#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
const int MAX_N = 1005;
const int inf = 1 << 20;
struct edge
{
	int from;
	int to;
	int cost;
};
vector<edge> es;
int d[MAX_N];
int main()
{
	int n, ml, md;
	cin >> n >> ml >> md;
	fill(d, d + MAX_N, inf); // 初始化距离数组
	d[1] = 0;
	
	while (ml--)
	{
		int al, bl, dl;
		scanf("%d %d %d", &al, &bl, &dl);
		edge e;
		e.from = al;
		e.to = bl;
		e.cost = dl;
		es.push_back(e);
	}
	while (md--)
	{
		int ad, bd, dd;
		scanf("%d %d %d", &ad, &bd, &dd);
		edge e;
		e.from = bd;
		e.to = ad;
		e.cost = -dd; // 注意：这里是负边，用负数表示
		es.push_back(e);
	}	
	for (int i = 0; i <= n; i++) // Bellman-Ford 算法
	{	
		for (int j = 2; j <= n; j++)
		{
			if (d[j] < inf)
			{
				d[j - 1] = min(d[j - 1], d[j]); // 更新距离数组		
			}
		}
		for (int j = 0; j < es.size(); j++)
		{
			edge e = es[j];
			if (d[e.to] > d[e.from] + e.cost)
			{
				d[e.to] = d[e.from] + e.cost;
				if (i == n) // 检测负环路
				{
					cout << "-1";
					return 0;
				}							
			}
		}		
	}	
	if (d[n] >= inf) // 若距离为初始值，则表示走不通
		d[n] = -2;
	cout << d[n]; // 输出结果
	return 0;
}
# 数论


# 辗转相除法


# 最大公约数




思路：暴力检查所有点，复杂度 o（|x1-x2|*|y1-y2|）。画图可以得出答案是 | x1-x2| |y1-y2 | 最大公约数 - 1。那么如何求最大公约数呢？这里用到辗转相除法。


辗转相除法，又称欧几里德算法，用于求两个整数的最大公约数（Greatest Common Divisor，简称 GCD）。算法基于以下定理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。


辗转相除法的步骤如下：


    

  1. 用较大数除以较小数，得到余数。
    2. 

  2. 将较小数作为新的被除数，余数作为新的除数，继续相除，直到余数为 0。
    3. 

  3. 最后一次相除的除数就是最大公约数。
    4. 



#include <iostream>
using namespace std;
// 辗转相除法求最大公约数
int gcd(int a, int b) {
    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}
int main() {
    int num1, num2;
    cout << "输入两个整数：" << endl;
    cin >> num1 >> num2;
    int result = gcd(num1, num2);
    cout << "它们的最大公约数是：" << result << endl;
    return 0;
}
# 有关素数的基础算法


素数是大于 1 的自然数中，除了 1 和本身外没有其他因数的数。换句话说，只能被 1 和自身整除的数被称为素数。


以下是一些前几个素数的例子：


    

  • 2 是最小的素数。
    • 

  • 3, 5, 7, 11, 13, 17, 19, 23, 29 是前面几个素数。
    • 



判断一个数是否为素数通常需要遍历从 2 到该数的平方根范围内的数来进行验证。如果该数可以被其中任何一个数整除，那么它就不是素数。


#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}
int main() {
    int num;
    cout << "输入一个整数：" << endl;
    cin >> num;
    if (isPrime(num)) {
        cout << num << " 是素数。" << endl;
    } else {
        cout << num << " 不是素数。" << endl;
    }
    return 0;
}
# 埃氏筛法


埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种用来查找一定范围内所有素数的古老而有效的算法。这个算法以希腊数学家埃拉托斯特尼的名字命名。


算法的基本思想是从 2 开始，将每个素数的各个倍数标记为非素数，直到不能再继续为止。具体步骤如下：


    

  1. 初始化一个布尔数组，用来表示从 2 到 n 之间的所有数，初始值都为 true，表示都是素数。
    2. 

  2. 从 2 开始遍历到 n 的开跟：

      

    • 如果当前数字 i 是素数（即布尔数组中对应的值为 true），则将 i 的所有倍数标记为非素数（将布尔数组中对应位置的值设为 false）。
      • 

    

    3. 

  3. 遍历结束后，所有值为 true 的位置对应的数字就是素数。
    4. 



#include <iostream>
#include <vector>
using namespace std;
vector<int> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n+1, true);
    vector<int> primes;
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }
    for (int p = 2; p <= n; p++) {
        if (isPrime[p]) {
            primes.push_back(p);
        }
    }
    return primes;
}
int main() {
    int N;
    cout << "请输入一个整数 N：" << endl;
    cin >> N;
    vector<int> result = sieveOfEratosthenes(N);
    cout << "小于等于 " << N << " 的所有素数为：" << endl;
    for (int prime : result) {
        cout << prime << " ";
    }
    cout << endl;
    return 0;
}
# 区间筛选


区间筛法是一种用于找出某一区间内所有素数的算法，它是埃拉托斯特尼筛法的一种变体。区间筛法通常用于在给定的区间内高效地找出所有素数。


#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// 区间筛法找出给定区间 [low, high] 内的所有素数
void segmentedSieve(int low, int high) {
    // 计算 sqrt (high)，作为标记数组的上限
    int limit = floor(sqrt(high)) + 1;
    // 初始化标记数组和素数数组
    vector<bool> isPrime(limit + 1, true);
    vector<int> primes;
    
    // 使用埃拉托斯特尼筛法在 [2, sqrt (high)] 范围内找出素数
    for (int p = 2; p * p <= limit; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= limit; i += p) {
                isPrime[i] = false;
            }
        }
    }
    // 将筛选出的素数存入 primes 数组中
    for (int p = 2; p <= limit; p++) {
        if (isPrime[p]) {
            primes.push_back(p);
        }
    }
    // 初始化区间内的标记数组，初始都为素数
    vector<bool> isPrimeRange(high - low + 1, true);
    // 对每个素数进行区间筛法
    for (int prime : primes) {
        int start = ceil((double)low / prime) * prime;
        for (int i = max(start, prime * prime); i <= high; i += prime) {
            isPrimeRange[i - low] = false;
        }
    }
    // 输出区间内的所有素数
    for (int i = low; i <= high; i++) {
        if (i >= 2 && isPrimeRange[i - low]) {
            cout << i << " ";
        }
    }
}
int main() {
    int low, high;
    cout << "请输入区间的下界和上界：" << endl;
    cin >> low >> high;
    cout << "区间 [" << low << ", " << high << "] 内的所有素数为：" << endl;
    segmentedSieve(low, high);
    cout << endl;
    return 0;
}
# 快速幂


问题：快速求出 a^k mod p 的结果，时间复杂度为 O (logk)，其中 a,p,k 为 10 的 9 次方。


暴力：


res = 1;
for(int i  = 1; i <= k; i++)
{
	res = res * a mod p;//k 次后再取模
}
// 时间复杂度 O (k);
# 反复平方法


方法是将 a^k 拆成若干项相乘的形式，即把 k 化成二进制形式，变成 2 的幂次相加。


反复平方法（快速幂算法）是一种用来快速计算一个数的整数次幂的算法。它利用了幂运算的一些性质，通过将指数进行二进制拆分的方式，减少了运算的次数，从而提高了计算效率。


下面是反复平方法的基本实现步骤：


    

  1. 将指数 (k) 表示为其二进制形式，例如：
    2. 

  2. 初始化一个变量  res  为 1，表示结果。
    3. 

  3. 从高位到低位依次处理二进制表达中的每一位：

      

    • 如果当前位 (b_i = 1)，则将结果乘以基数 ( a ) 并取模 ( p )。
      • 

    • 在每一步中，基数 (a) 都会自乘以自身并取模 ( p )。
      • 

    

    4. 

  4. 循环结束后，返回结果  res 。
    5. 



这样，通过对指数进行二进制拆分和利用幂运算的性质，可以大大减少计算的次数，从而提高了计算效率。


int fastExpoMod(int a, int k, int p) {
    long long res = 1;                    // 初始化结果为 1
    long long base = a % p;                // 初始化底数为 a mod p
    while (k > 0) {                        // 当指数大于 0 时进行循环
        if (k % 2 == 1) {                  // 如果当前指数的最低位为 1
            res = (res * base) % p;        // 更新结果为 (res * base) mod p
        }
        base = (base * base) % p;          // 更新底数为 (base^2) mod p
        k /= 2;                            // 将指数右移一位，相当于除以 2
    }
    return (int)res;                       // 返回结果，注意转换为 int 类型
}
int result = fastExpoMod(2, 5, 7);         // 调用函数计算 2^5 mod 7 的结果