一、引言：超越一维的数字我们对数字的认知，始于在数轴上左右移动的整数与实数。这是一个一维的世界。然而，在广阔的算法问题域中，我们频繁面对二维乃至更高维度的结构：平面上的点、向量的旋转、周期性的变换。将这些二维问题强行压缩到一维的实数轴上处理，往往会使问题变得复杂、表达式冗长、几何直觉尽失。
复数，正是为了优雅地描述二维世界而生的数学工具。一个复数 内含了两个独立的信息（实部 和虚部 ），...
在算法的世界中，效率是衡量优劣的核心标尺。一个看似简单的操作，如求幂 ，其背后可能隐藏着巨大的优化空间。本文将系统性地剖析快速幂（Fast Exponentiation）算法，从其数学原理出发，深入探讨其在不同场景下的实现、变种及其与其他算法思想的深刻联系。我们的目标不仅是理解快速幂是什么，更是要掌握其思想精髓，并能灵活地将其应用到更广泛的问题域中。
1. 问题的源起：朴素的求幂我们面临的第...
1. 万物皆数，从二进制谈起在深入任何技巧之前，我们必须回到原点。计算机科学的宏伟大厦，建立在坚实的二进制地基之上。
1.1 为何是二进制？我们生活在十进制的世界，因为我们有十根手指。而计算机的世界，建立在晶体管之上。晶体管最稳定、最易于区分的状态只有两种：导通（高电平）和截止（低电平）。这两种状态，天然地对应了数学中的两个符号：1和0。这种选择并非偶然，而是物理现实与信息表达之间最经济、最...
ST表我们时常会遇到对一个固定序列进行反复区间查询的问题。例如，查询一个给定区间内的最大值、最小值，或是最大公约数等。这类问题统称为静态区间查询问题，因为数据序列本身不会发生改变。对于这类问题，如果每次查询都暴力扫描一遍区间，当查询次数较多时，时间复杂度往往难以承受。ST表（Sparse Table，稀疏表）算法应运而生，它是一种基于倍增思想的预处理技术，能够在 的预处理后，以 的惊人效...
第一章：引言与背景1.1 贝祖定理的历史与命名贝祖定理得名于法国数学家 贝祖（Étienne Bézout），他在18世纪提出了这个定理，并且它在数论中占据了举足轻重的地位。贝祖定理最初的提出旨在探讨整数之间的线性关系，尤其在解决整数的最大公约数问题中具有重要应用。值得注意的是，尽管贝祖定理在西方数学中由贝祖提出，但在古代中国的数学经典中，也早有类似思想的体现，特别是在《九章算术》中的线性同...
莫比乌斯反演（Möbius inversion）是一种在数论中非常重要的工具，用于将一些累积求和公式反转。它通常用于处理数值序列的转换，尤其是在处理数学函数的和式时。简而言之，莫比乌斯反演允许我们通过已知的累积（或前缀和）公式，恢复原始的序列。
概念假设我们有一个数列 和 ，它们之间通过以下关系关联：
其中， 表示 是 的约数，求和是对所有 的约数进行的。
莫比乌斯反演的核心思想就...
在算法竞赛，数论是绕不开的话题，而素数（或称质数）则是数论中最基础也最重要的核心概念之一。无论是直接考察素数性质，还是作为其他数论算法（如欧拉函数、模运算、因数分解）的基础，对素数深刻的理解和高效的算法掌握都是冲击奖牌的关键。
1. 素数基础 (Prime Basics)1.1 定义一个大于 1 的正整数 ，如果除了 1 和它本身以外，不能被其他正整数整除，那么 就被称为素数（质数）。大于...
一、整除、素数与最大公约数这是数论大厦的地基，看似简单，却蕴含着后续一切知识的基础。
1. 整除性 (Divisibility)如果整数 a 除以非零整数 b，商为整数 q 且余数为 0，我们就说 b 整除 a，或者 a 是 b 的倍数，b 是 a 的约数（或因子）。记作 b | a。
性质：
自反性：a | a
传递性：若 a | b 且 b | c，则 a | c
若 a | b 且 ...
一、引言：问题的起源在算法竞赛的数学部分中，同余理论是一个重要部分。它以一种优雅的方式将无限的整数世界映射到有限的剩余类中，为我们处理与整除、余数、周期性相关的问题提供了独特的视角。而当我们将同余理论与图论中的最短路算法相结合时，一个精巧的算法模型——同余最短路——便应运而生。
这个模型专门解决一类特定形式的问题：给定 个正整数 ，问它们通过非负整数系数的线性组合 () 能够表示出哪些数...
1. 图的构成网络流问题通常在一个有向图中求解，这个图由以下几个部分构成：
节点（Vertex）：表示网络中的不同点，如城市、站点等。
边（Edge）：表示连接两个节点的路径，每条边有一个容量，即该边能够传输的最大流量。
源点（Source）：流量的起始节点，通常标记为 S。
汇点（Sink）：流量的终点节点，通常标记为 T。
2. 流量和容量
流量（Flow）：从源点到汇点传递的“物品...
