1. 项目概述算法竞赛与日常开发中的数学基石看到这个标题很多朋友可能会心一笑。这哪里是一个“项目”分明是算法竞赛选手和日常开发中处理数学逻辑时手边必备的一堆“轮子”合集。没错这就是一个关于基础数学算法模板的总结。素数判定、质因数分解、最大公约数、高精度运算、二分查找、前缀和——这些概念单独拎出来可能只是教科书里的一个章节但当你真正投身于解决复杂的编程问题无论是参加在线评测OJ还是开发需要高性能计算的业务模块时你会发现它们就像螺丝刀、扳手一样是最基础、最常用也最考验功底的“工具”。我整理这份总结的初衷源于无数次在深夜调试代码时的顿悟和踩坑经历。比如明明知道该用筛法求素数却因为数组开小了或者边界没处理好导致WA错误答案高精度加法写出来了但处理正负号和前导零时总是一团糟二分查找看似简单但循环条件和更新边界的细节稍有偏差结果就天差地别。这些算法模板其核心思想往往简洁优美但魔鬼全藏在实现细节和边界条件里。这份总结就是试图把这些散落在各处的“珍珠”串起来并结合我个人的实战经验把那些容易忽略的“坑点”和“优化技巧”讲清楚让你在需要时能快速、准确地“抄作业”甚至能理解为什么这么写是更好的。2. 核心算法模板深度解析与实现2.1 素数判定与质因数分解从暴力到高效素数质数是数论的基石相关问题在编程中极为常见。最朴素的想法是对于一个正整数n用2到sqrt(n)之间的所有整数去试除。这是理解素数概念的起点但效率太低一旦n的范围达到10^6甚至更大就需要更高效的算法。2.1.1 埃拉托斯特尼筛法埃筛这是最经典的素数筛选算法用于快速得到某一范围内所有的素数。其核心思想是从2开始将每个素数的倍数标记为合数。def sieve_of_eratosthenes(n): 返回小于n的所有素数列表。 时间复杂度: O(n log log n) 空间复杂度: O(n) is_prime [True] * (n) # 索引代表数字True表示是素数 is_prime[0] is_prime[1] False # 0和1不是素数 for i in range(2, int(n**0.5) 1): # 只需遍历到sqrt(n) if is_prime[i]: # 从i*i开始标记因为如2*i, 3*i ... (i-1)*i 已经被更小的素数标记过了 for j in range(i*i, n, i): is_prime[j] False # 收集所有素数 primes [i for i in range(2, n) if is_prime[i]] return primes注意内层循环的起始点j i*i是一个关键优化。如果从j 2*i开始会重复标记。例如i5时102*5早已被i2标记过。2.1.2 线性筛法欧拉筛埃筛的一个问题是有些合数会被多个素数重复标记如12会被2和3各标记一次。线性筛保证了每个合数只被其最小质因子标记一次从而达到严格O(n)的时间复杂度。这在n极大如10^7时优势明显。def linear_sieve(n): 线性筛法返回小于n的所有素数列表。 每个合数只被其最小质因子筛掉一次。 is_prime [True] * n primes [] # 用于存储所有找到的素数 for i in range(2, n): if is_prime[i]: primes.append(i) # i是素数 # 遍历当前已找到的所有素数 for p in primes: if i * p n: break is_prime[i * p] False # 标记合数 i*p # 关键步骤如果p能整除i则停止内层循环 # 这保证了每个合数只被其最小质因子标记 # 例如当i4, p2时标记8后因为4%20跳出循环。 # 这样合数12将在i6, p2时被标记而不是在i4, p3时。 if i % p 0: break return primes2.1.3 质因数分解将一个合数分解为若干个质因数的乘积是解决许多数论问题如求约数个数、欧拉函数等的前提。基于试除法的分解是最常用的方法。def prime_factorization(n): 质因数分解返回一个列表每个元素为 (质因数, 指数) 的元组。 例如prime_factorization(84) 返回 [(2, 2), (3, 1), (7, 1)]因为 84 2^2 * 3 * 7 factors [] # 首先处理因子2可以加速后续奇数因子的判断 cnt 0 while n % 2 0: cnt 1 n // 2 if cnt 0: factors.append((2, cnt)) # 处理奇数因子只需试除到 sqrt(n) i 3 while i * i n: cnt 0 while n % i 0: cnt 1 n // i if cnt 0: factors.append((i, cnt)) i 2 # 只检查奇数 # 如果最后剩余的n大于1那么它本身就是一个质数 if n 1: factors.append((n, 1)) return factors实操心得在分解前先单独处理2然后以2为步长递增这是一个非常实用的优化。因为偶数中只有2是质数这样可以直接跳过所有其他偶数因子。2.2 最大公约数与最小公倍数欧几里得的智慧最大公约数GCD和最小公倍数LCM是另一组孪生概念在化简分数、判断数的整除性、解决同余方程等问题中无处不在。2.2.1 辗转相除法欧几里得算法这是计算GCD最著名且高效的算法。其原理基于一个核心等式gcd(a, b) gcd(b, a % b)。递归或迭代实现都非常简洁。def gcd_euclidean(a, b): 使用欧几里得算法计算最大公约数递归版本。 if b 0: return a return gcd_euclidean(b, a % b) def gcd_iterative(a, b): 使用欧几里得算法计算最大公约数迭代版本更优。 while b ! 0: a, b b, a % b return aPython的标准库math中已经提供了高度优化的math.gcd()函数在绝大多数情况下应优先使用它。2.2.2 最小公倍数与多个数的GCD/LCM利用公式lcm(a, b) a * b / gcd(a, b)可以轻松求出最小公倍数。注意先做除法再乘法防止中间结果溢出在Python大整数中问题不大但在C/Java中需注意。import math def lcm(a, b): return a // math.gcd(a, b) * b # 先除后乘避免溢出 # 计算多个数的最大公约数 def gcd_of_list(nums): result nums[0] for num in nums[1:]: result math.gcd(result, num) if result 1: # 提前终止优化 break return result # 计算多个数的最小公倍数 def lcm_of_list(nums): result 1 for num in nums: result lcm(result, num) return result注意事项当数字非常大时直接a * b可能导致溢出即使在Python中超大数乘法也会消耗更多时间和内存。因此lcm函数中a // gcd(a, b) * b的写法是更安全的。2.3 高精度运算当内置类型不够用时Python的整数类型本身是“高精度”的理论上可以处理任意大的整数受限于内存。但在C、Java等语言中基本数据类型如int,long long有固定位数限制。模拟大整数的运算高精度就成了必备技能。其核心思想是用数组或字符串来存储数字的每一位。2.3.1 高精度加法从最低位开始逐位相加处理进位。def high_precision_add(num1_str, num2_str): 字符串形式的高精度加法返回结果字符串。 假设输入为非负整数。 # 反转字符串方便从个位开始计算 a num1_str[::-1] b num2_str[::-1] # 补齐长度 max_len max(len(a), len(b)) a a.ljust(max_len, 0) b b.ljust(max_len, 0) result [] carry 0 for i in range(max_len): digit_sum int(a[i]) int(b[i]) carry carry digit_sum // 10 result.append(str(digit_sum % 10)) # 处理最后的进位 if carry: result.append(str(carry)) # 反转回来并去除可能的前导零除了结果本身就是0 sum_str .join(result[::-1]).lstrip(0) return sum_str if sum_str else 02.3.2 高精度减法同样从最低位开始处理借位。需要先判断两个数的大小确保用大数减小数最终结果处理符号。def high_precision_sub(num1_str, num2_str): 高精度减法返回 num1 - num2 的结果字符串。 假设 num1 num2 0。 # 确保 num1 num2 if len(num1_str) len(num2_str) or (len(num1_str) len(num2_str) and num1_str num2_str): # 在实际应用中这里应返回负号并交换两数计算。此处简化为假设已处理。 raise ValueError(num1 must be greater than or equal to num2 for this simplified version.) a num1_str[::-1] b num2_str[::-1].ljust(len(a), 0) result [] borrow 0 for i in range(len(a)): digit_a int(a[i]) digit_b int(b[i]) # 当前位被借位后的值 current digit_a - borrow - digit_b if current 0: current 10 borrow 1 else: borrow 0 result.append(str(current)) # 去除结果中的前导零 sum_str .join(result[::-1]).lstrip(0) return sum_str if sum_str else 0踩坑记录高精度减法的边界情况特别多。一是要处理被减数小于减数的情况这时结果应为负数。二是要仔细处理借位的传递尤其是在连续多位为0时借位。三是一定要记得去除结果中的前导零但也要保留“0”本身。2.3.3 高精度乘法大数乘小数这里展示一个高精度数乘以一个普通整数int范围内的简化版本这是更常见的场景如阶乘计算。def high_precision_mul_big_small(num_str, small_int): 高精度数字符串乘以一个较小的整数。 if small_int 0: return 0 a num_str[::-1] result [] carry 0 for digit_char in a: product int(digit_char) * small_int carry carry product // 10 result.append(str(product % 10)) while carry 0: result.append(str(carry % 10)) carry // 10 # 去除前导零通常不会出现除非原数为0 product_str .join(result[::-1]).lstrip(0) return product_str if product_str else 0 # 示例计算 100! 的近似通过连续乘 def factorial_approx(n): result 1 for i in range(2, n1): result high_precision_mul_big_small(result, i) return result对于“大数×大数”通常需要模拟竖式乘法复杂度为O(n*m)可以使用Karatsuba等更高效的算法进行优化但在竞赛和大多数应用中上述简化版已足够。2.4 二分查找函数细节决定成败二分查找的思想极其简单在一个有序序列中通过不断缩小搜索范围来定位目标。但写出一个完全正确、没有死循环、能处理各种边界条件的二分查找却并不容易。核心在于循环不变量的维护。2.4.1 精确查找模板查找有序数组arr中第一个等于目标值target的位置左边界。def binary_search_left(arr, target): 在升序数组arr中寻找第一个 target 的元素的索引。 如果所有元素都小于target则返回len(arr)。 这可以用来查找target的左边界。 left, right 0, len(arr) # 注意右边界是len(arr)这是一个“左闭右开”区间 [left, right) while left right: # 因为区间是左闭右开所以当leftright时区间为空循环结束 mid left (right - left) // 2 # 防止(leftright)溢出 if arr[mid] target: left mid 1 # 目标在右半部分且mid肯定不是解 else: # arr[mid] target right mid # 目标在左半部分mid有可能是解第一个target的所以保留 return left # 此时leftright且是第一个target的位置 # 查找target是否存在并返回其左边界 def find_target_left(arr, target): idx binary_search_left(arr, target) # 检查找到的位置是否越界以及该位置的值是否等于target if idx len(arr) and arr[idx] target: return idx else: return -1 # 表示未找到2.4.2 查找右边界模板查找有序数组arr中最后一个等于目标值target的位置。def binary_search_right(arr, target): 在升序数组arr中寻找最后一个 target 的元素的索引。 如果所有元素都大于target则返回-1。 这可以用来查找target的右边界。 left, right -1, len(arr) - 1 # 初始化为“左开右闭”区间 (left, right] while left right: # 注意当区间长度为2时(leftright)//2会向下取整到left可能导致死循环。 # 因此需要向上取整。 mid left (right - left 1) // 2 # 关键1确保mid偏向右侧 if arr[mid] target: right mid - 1 # 目标在左半部分mid肯定不是解 else: # arr[mid] target left mid # 目标在右半部分mid有可能是解最后一个target的所以保留 return left # 此时leftright且是最后一个target的位置 def find_target_right(arr, target): idx binary_search_right(arr, target) if idx 0 and arr[idx] target: return idx else: return -1核心技巧二分查找的难点在于mid的取整方式和left/right的更新策略。记住一个原则根据区间的定义来决定如何更新边界。如果区间是[left, right]左闭右闭那么while left right更新时left mid 1或right mid - 1。如果区间是[left, right)左闭右开那么while left right更新时left mid 1或right mid。选择一种并始终坚持可以避免大多数错误。2.5 前缀和与差分区间操作的利器前缀和是一种预处理技术能在O(1)时间内查询数组任意区间的和。差分是其逆运算能高效地对区间进行批量增减操作。2.5.1 一维前缀和def build_prefix_sum(arr): 构建前缀和数组。 prefix[i] 表示 arr[0] arr[1] ... arr[i-1] (前i个元素的和) 通常令 prefix[0] 0这样区间 [l, r] 的和就是 prefix[r1] - prefix[l] n len(arr) prefix [0] * (n 1) for i in range(n): prefix[i 1] prefix[i] arr[i] return prefix def range_sum(prefix, l, r): 查询原数组arr中区间[l, r]的和闭区间 return prefix[r 1] - prefix[l]2.5.2 一维差分差分数组diff满足arr[i] diff[0] diff[1] ... diff[i]。对原数组arr的区间[l, r]统一加上val等价于在差分数组上只修改两个点diff[l] val和diff[r1] - val。def build_diff(arr): 构建差分数组。假设原数组初始全为0经过若干次区间加操作后得到arr。 n len(arr) diff [0] * (n 1) # 多一位方便处理 r1 的边界 # 实际上如果arr是初始数组可以认为它是由对每个位置[i,i]加arr[i]操作得到的。 # 更常见的用法是初始一个全零数组通过差分进行区间操作最后通过前缀和还原。 for i in range(n): # 模拟在区间[i, i]上增加arr[i] diff[i] arr[i] diff[i 1] - arr[i] return diff def apply_diff(initial_arr, diff): 应用差分数组得到操作后的结果数组 n len(initial_arr) result [0] * n current 0 for i in range(n): current diff[i] result[i] initial_arr[i] current return result # 更常用的模式直接进行区间加操作 def range_add_using_diff(diff, l, r, val): 对差分数组diff进行操作表示对原数组区间[l, r]增加val diff[l] val if r 1 len(diff): diff[r 1] - val2.5.3 二维前缀和与差分扩展到二维矩阵原理类似但公式稍复杂。二维前缀和prefix[i][j]表示从(0,0)到(i-1, j-1)的子矩阵和。构建prefix[i][j] matrix[i-1][j-1] prefix[i-1][j] prefix[i][j-1] - prefix[i-1][j-1]查询以(x1,y1)为左上角(x2,y2)为右下角的子矩阵和sum prefix[x21][y21] - prefix[x1][y21] - prefix[x21][y1] prefix[x1][y1]二维差分对子矩阵(x1,y1)到(x2,y2)统一加val等价于在差分矩阵上修改四个点。应用场景前缀和与差分是解决“静态区间求和”和“区间批量更新”问题的标准武器。例如频繁查询数组某个区间的和、计算矩阵中特定子矩阵的元素和、对数组的某个区间所有元素同时加一个数等。在数据量大、操作频繁时能将复杂度从O(n)降至O(1)。3. 模板的整合应用与实战场景掌握了这些独立的模板就像拥有了各种精良的工具。但真正的挑战在于如何根据具体问题灵活地将它们组合起来使用。下面通过几个典型场景来分析。3.1 场景一求解一个大数的所有质因数并计算其约数个数这综合了质因数分解和数论知识。根据算术基本定理一个数N分解为p1^a1 * p2^a2 * ... * pk^ak那么它的正约数个数就是(a11)*(a21)*...*(ak1)。def count_divisors(n): 计算正整数n的正约数个数 factors prime_factorization(n) # 使用前面定义的质因数分解函数 count 1 for _, exp in factors: count * (exp 1) return count # 示例求 100 的约数个数。100 2^2 * 5^2 约数个数 (21)*(21)9 print(count_divisors(100)) # 输出: 93.2 场景二使用二分查找结合前缀和解决问题LeetCode上有一道经典题目“长度最小的子数组”给定一个含有n个正整数的数组和一个正整数target找出该数组中满足其和≥ target的长度最小的连续子数组。 暴力解法是O(n^2)。更优的解法是使用前缀和二分查找复杂度O(n log n)。计算前缀和数组prefix。遍历每个起始位置i我们需要找到最小的j使得prefix[j] - prefix[i] target。这等价于在prefix数组中从i1开始二分查找第一个 prefix[i] target的位置。def min_subarray_len(target, nums): n len(nums) if n 0: return 0 # 构建前缀和 prefix [0] * (n 1) for i in range(n): prefix[i 1] prefix[i] nums[i] min_len float(inf) for i in range(n): sum_to_find prefix[i] target # 在prefix[i1:]中二分查找第一个 sum_to_find 的位置 # 使用自定义的二分查找左边界函数 left, right i 1, n 1 # 在prefix数组的[i1, n]区间查找 while left right: mid left (right - left) // 2 if prefix[mid] sum_to_find: left mid 1 else: right mid j left if j n: # 找到了 min_len min(min_len, j - i) return 0 if min_len float(inf) else min_len当然这道题用滑动窗口可以达到O(n)的线性时间复杂度但“前缀和二分”的思路是一种更通用的范式适用于原数组元素不是正数或者需要查询多次不同target的情况。3.3 场景三高精度运算在组合数学中的应用计算组合数C(n, m)当n和m很大时直接计算阶乘会溢出。可以利用公式C(n, m) n! / (m! * (n-m)!)并结合质因数分解与高精度乘法来避免中间过程的溢出。将分子n!的质因数分解结果与分母m!和(n-m)!的质因数分解结果相减指数相减。将剩余质因数的幂次用高精度乘法乘起来。def factorial_prime_factorization(n): 计算n!的质因数分解返回字典{质数: 指数} # 一种高效方法对于每个质数p计算n!中p的指数为 [n/p] [n/p^2] [n/p^3] ... # 这里为了清晰使用另一种方法对1到n每个数分解质因数然后合并适用于n不太大时 from collections import defaultdict factor_count defaultdict(int) for i in range(2, n 1): factors prime_factorization(i) for p, exp in factors: factor_count[p] exp return factor_count def combination_prime(n, m): 使用质因数分解计算C(n, m) if m n or m 0: return 0 # 计算 n!, m!, (n-m)! 的质因数分解 fact_n factorial_prime_factorization(n) fact_m factorial_prime_factorization(m) fact_nm factorial_prime_factorization(n - m) # 合并结果: C(n,m) n! / (m! * (n-m)!) result_factors {} for p in fact_n: exp fact_n[p] - fact_m.get(p, 0) - fact_nm.get(p, 0) if exp 0: result_factors[p] exp # 将质因数表示的高精度数乘起来 result 1 for p, exp in result_factors.items(): # 计算 p^exp 用快速幂思想结合高精度乘法 power_str str(p) # 快速幂计算 p^exp e exp while e 0: if e % 2 1: result high_precision_mul_big_small(result, int(power_str)) power_str high_precision_mul_big_small(power_str, int(power_str)) # 平方 e // 2 return result这种方法虽然代码稍长但能精确计算非常大的组合数是处理大数组合问题的可靠方法。4. 常见问题、调试技巧与性能优化即使有了模板在实际编码和调试中还是会遇到各种问题。下面分享一些我积累的经验和常见陷阱。4.1 素数筛法中的典型错误数组大小错误埃筛或线性筛的数组通常需要开到n1或n用于表示数字0到n-1或1到n。务必明确下标与数字的对应关系否则会导致数组越界或漏判。循环边界不清埃筛的外层循环for i in range(2, int(n**0.5)1)必须是 sqrt(n)。内层循环for j in range(i*i, n, i)的起始点i*i是优化要理解其原理。线性筛的if i % p 0: break这是保证线性的关键务必牢记。它确保了每个合数i*p只被其最小质因子p筛掉。4.2 二分查找的“死循环”与边界错误这是二分查找的重灾区。死循环通常发生在while left right且更新策略为left mid或right mid时。如果计算mid是向下取整(leftright)//2当left和right相差1时mid会等于left。如果此时分支走向是left mid那么区间将不会缩小导致死循环。解决方案在需要保留mid的情况下让mid向上取整(leftright1)//2。找不到元素检查循环结束后left或right指向的位置是否有效在数组范围内以及该位置的值是否等于目标值。通用调试技巧在循环内打印left,right,mid的值以及arr[mid]与target的比较结果这是理解二分过程最直观的方法。对于复杂问题可以先用小规模数据手动模拟。4.3 高精度运算的细节陷阱前导零处理在完成加法、乘法运算后反转回来的字符串可能有多余的前导零如000123。必须使用.lstrip(0)去除但要小心结果本身就是0的情况去除后会变成空字符串需要特殊处理if sum_str else 0。进位/借位的最终处理在循环结束后一定要检查最后的carry或borrow是否为非零并妥善处理。符号处理减法必须考虑正负。一个稳健的实现是先比较两个绝对值大小决定结果符号然后用大绝对值减去小绝对值。性能优化对于极长数字的乘法Python内置的int类型已经高度优化通常比自己实现的高精度字符串算法快得多。只有在教学或特定限制如其他语言下才需要手动实现。但在C中手写高精度是常态。4.4 前缀和与差分的索引偏移这是最容易出错的地方。为了让公式统一区间[l, r]的和等于prefix[r1] - prefix[l]我们通常定义prefix[0] 0prefix[i]表示前i个元素的和下标从0到i-1。务必在脑海中明确prefix数组的下标含义。画图是理清关系的最好方法。4.5 性能考量与工具选择素数判定对于单个大数的素数判定除了试除法还有Miller-Rabin概率素性测试速度更快适用于极大数如密码学领域。GCD计算Python的math.gcd是用C实现的效率极高绝对优于任何手写Python版本。多个数的GCD/LCM使用functools.reduce配合math.gcd/lcm函数非常优雅。import math, functools nums [12, 18, 24] gcd_val functools.reduce(math.gcd, nums) lcm_val functools.reduce(lambda x, y: x // math.gcd(x, y) * y, nums)二分查找Python的bisect模块提供了现成的二分查找函数bisect_left,bisect_right其实现经过优化且无bug在允许使用标准库时应作为首选。高精度运算如前所述在Python中除非有特殊限制如模拟算法过程否则直接使用int类型。需要处理浮点数高精度时可以考虑decimal模块。把这些基础模板练到肌肉记忆里理解其每一个细节和变体在遇到复杂问题时你就能像搭积木一样快速组合出解决方案。编程竞赛和工程中的很多难题拆解到底层往往就是这些基础算法的巧妙结合。这份总结不是终点而是一个随时可以回来查阅、修正和补充的起点。在实际编码中最宝贵的经验往往来自于调试那些因为一个等号、一个边界条件而浪费的几个小时希望我的这些踩坑记录能帮你绕过一些弯路。
算法竞赛与开发必备：素数筛法、二分查找与高精度运算模板精讲
1. 项目概述算法竞赛与日常开发中的数学基石看到这个标题很多朋友可能会心一笑。这哪里是一个“项目”分明是算法竞赛选手和日常开发中处理数学逻辑时手边必备的一堆“轮子”合集。没错这就是一个关于基础数学算法模板的总结。素数判定、质因数分解、最大公约数、高精度运算、二分查找、前缀和——这些概念单独拎出来可能只是教科书里的一个章节但当你真正投身于解决复杂的编程问题无论是参加在线评测OJ还是开发需要高性能计算的业务模块时你会发现它们就像螺丝刀、扳手一样是最基础、最常用也最考验功底的“工具”。我整理这份总结的初衷源于无数次在深夜调试代码时的顿悟和踩坑经历。比如明明知道该用筛法求素数却因为数组开小了或者边界没处理好导致WA错误答案高精度加法写出来了但处理正负号和前导零时总是一团糟二分查找看似简单但循环条件和更新边界的细节稍有偏差结果就天差地别。这些算法模板其核心思想往往简洁优美但魔鬼全藏在实现细节和边界条件里。这份总结就是试图把这些散落在各处的“珍珠”串起来并结合我个人的实战经验把那些容易忽略的“坑点”和“优化技巧”讲清楚让你在需要时能快速、准确地“抄作业”甚至能理解为什么这么写是更好的。2. 核心算法模板深度解析与实现2.1 素数判定与质因数分解从暴力到高效素数质数是数论的基石相关问题在编程中极为常见。最朴素的想法是对于一个正整数n用2到sqrt(n)之间的所有整数去试除。这是理解素数概念的起点但效率太低一旦n的范围达到10^6甚至更大就需要更高效的算法。2.1.1 埃拉托斯特尼筛法埃筛这是最经典的素数筛选算法用于快速得到某一范围内所有的素数。其核心思想是从2开始将每个素数的倍数标记为合数。def sieve_of_eratosthenes(n): 返回小于n的所有素数列表。 时间复杂度: O(n log log n) 空间复杂度: O(n) is_prime [True] * (n) # 索引代表数字True表示是素数 is_prime[0] is_prime[1] False # 0和1不是素数 for i in range(2, int(n**0.5) 1): # 只需遍历到sqrt(n) if is_prime[i]: # 从i*i开始标记因为如2*i, 3*i ... (i-1)*i 已经被更小的素数标记过了 for j in range(i*i, n, i): is_prime[j] False # 收集所有素数 primes [i for i in range(2, n) if is_prime[i]] return primes注意内层循环的起始点j i*i是一个关键优化。如果从j 2*i开始会重复标记。例如i5时102*5早已被i2标记过。2.1.2 线性筛法欧拉筛埃筛的一个问题是有些合数会被多个素数重复标记如12会被2和3各标记一次。线性筛保证了每个合数只被其最小质因子标记一次从而达到严格O(n)的时间复杂度。这在n极大如10^7时优势明显。def linear_sieve(n): 线性筛法返回小于n的所有素数列表。 每个合数只被其最小质因子筛掉一次。 is_prime [True] * n primes [] # 用于存储所有找到的素数 for i in range(2, n): if is_prime[i]: primes.append(i) # i是素数 # 遍历当前已找到的所有素数 for p in primes: if i * p n: break is_prime[i * p] False # 标记合数 i*p # 关键步骤如果p能整除i则停止内层循环 # 这保证了每个合数只被其最小质因子标记 # 例如当i4, p2时标记8后因为4%20跳出循环。 # 这样合数12将在i6, p2时被标记而不是在i4, p3时。 if i % p 0: break return primes2.1.3 质因数分解将一个合数分解为若干个质因数的乘积是解决许多数论问题如求约数个数、欧拉函数等的前提。基于试除法的分解是最常用的方法。def prime_factorization(n): 质因数分解返回一个列表每个元素为 (质因数, 指数) 的元组。 例如prime_factorization(84) 返回 [(2, 2), (3, 1), (7, 1)]因为 84 2^2 * 3 * 7 factors [] # 首先处理因子2可以加速后续奇数因子的判断 cnt 0 while n % 2 0: cnt 1 n // 2 if cnt 0: factors.append((2, cnt)) # 处理奇数因子只需试除到 sqrt(n) i 3 while i * i n: cnt 0 while n % i 0: cnt 1 n // i if cnt 0: factors.append((i, cnt)) i 2 # 只检查奇数 # 如果最后剩余的n大于1那么它本身就是一个质数 if n 1: factors.append((n, 1)) return factors实操心得在分解前先单独处理2然后以2为步长递增这是一个非常实用的优化。因为偶数中只有2是质数这样可以直接跳过所有其他偶数因子。2.2 最大公约数与最小公倍数欧几里得的智慧最大公约数GCD和最小公倍数LCM是另一组孪生概念在化简分数、判断数的整除性、解决同余方程等问题中无处不在。2.2.1 辗转相除法欧几里得算法这是计算GCD最著名且高效的算法。其原理基于一个核心等式gcd(a, b) gcd(b, a % b)。递归或迭代实现都非常简洁。def gcd_euclidean(a, b): 使用欧几里得算法计算最大公约数递归版本。 if b 0: return a return gcd_euclidean(b, a % b) def gcd_iterative(a, b): 使用欧几里得算法计算最大公约数迭代版本更优。 while b ! 0: a, b b, a % b return aPython的标准库math中已经提供了高度优化的math.gcd()函数在绝大多数情况下应优先使用它。2.2.2 最小公倍数与多个数的GCD/LCM利用公式lcm(a, b) a * b / gcd(a, b)可以轻松求出最小公倍数。注意先做除法再乘法防止中间结果溢出在Python大整数中问题不大但在C/Java中需注意。import math def lcm(a, b): return a // math.gcd(a, b) * b # 先除后乘避免溢出 # 计算多个数的最大公约数 def gcd_of_list(nums): result nums[0] for num in nums[1:]: result math.gcd(result, num) if result 1: # 提前终止优化 break return result # 计算多个数的最小公倍数 def lcm_of_list(nums): result 1 for num in nums: result lcm(result, num) return result注意事项当数字非常大时直接a * b可能导致溢出即使在Python中超大数乘法也会消耗更多时间和内存。因此lcm函数中a // gcd(a, b) * b的写法是更安全的。2.3 高精度运算当内置类型不够用时Python的整数类型本身是“高精度”的理论上可以处理任意大的整数受限于内存。但在C、Java等语言中基本数据类型如int,long long有固定位数限制。模拟大整数的运算高精度就成了必备技能。其核心思想是用数组或字符串来存储数字的每一位。2.3.1 高精度加法从最低位开始逐位相加处理进位。def high_precision_add(num1_str, num2_str): 字符串形式的高精度加法返回结果字符串。 假设输入为非负整数。 # 反转字符串方便从个位开始计算 a num1_str[::-1] b num2_str[::-1] # 补齐长度 max_len max(len(a), len(b)) a a.ljust(max_len, 0) b b.ljust(max_len, 0) result [] carry 0 for i in range(max_len): digit_sum int(a[i]) int(b[i]) carry carry digit_sum // 10 result.append(str(digit_sum % 10)) # 处理最后的进位 if carry: result.append(str(carry)) # 反转回来并去除可能的前导零除了结果本身就是0 sum_str .join(result[::-1]).lstrip(0) return sum_str if sum_str else 02.3.2 高精度减法同样从最低位开始处理借位。需要先判断两个数的大小确保用大数减小数最终结果处理符号。def high_precision_sub(num1_str, num2_str): 高精度减法返回 num1 - num2 的结果字符串。 假设 num1 num2 0。 # 确保 num1 num2 if len(num1_str) len(num2_str) or (len(num1_str) len(num2_str) and num1_str num2_str): # 在实际应用中这里应返回负号并交换两数计算。此处简化为假设已处理。 raise ValueError(num1 must be greater than or equal to num2 for this simplified version.) a num1_str[::-1] b num2_str[::-1].ljust(len(a), 0) result [] borrow 0 for i in range(len(a)): digit_a int(a[i]) digit_b int(b[i]) # 当前位被借位后的值 current digit_a - borrow - digit_b if current 0: current 10 borrow 1 else: borrow 0 result.append(str(current)) # 去除结果中的前导零 sum_str .join(result[::-1]).lstrip(0) return sum_str if sum_str else 0踩坑记录高精度减法的边界情况特别多。一是要处理被减数小于减数的情况这时结果应为负数。二是要仔细处理借位的传递尤其是在连续多位为0时借位。三是一定要记得去除结果中的前导零但也要保留“0”本身。2.3.3 高精度乘法大数乘小数这里展示一个高精度数乘以一个普通整数int范围内的简化版本这是更常见的场景如阶乘计算。def high_precision_mul_big_small(num_str, small_int): 高精度数字符串乘以一个较小的整数。 if small_int 0: return 0 a num_str[::-1] result [] carry 0 for digit_char in a: product int(digit_char) * small_int carry carry product // 10 result.append(str(product % 10)) while carry 0: result.append(str(carry % 10)) carry // 10 # 去除前导零通常不会出现除非原数为0 product_str .join(result[::-1]).lstrip(0) return product_str if product_str else 0 # 示例计算 100! 的近似通过连续乘 def factorial_approx(n): result 1 for i in range(2, n1): result high_precision_mul_big_small(result, i) return result对于“大数×大数”通常需要模拟竖式乘法复杂度为O(n*m)可以使用Karatsuba等更高效的算法进行优化但在竞赛和大多数应用中上述简化版已足够。2.4 二分查找函数细节决定成败二分查找的思想极其简单在一个有序序列中通过不断缩小搜索范围来定位目标。但写出一个完全正确、没有死循环、能处理各种边界条件的二分查找却并不容易。核心在于循环不变量的维护。2.4.1 精确查找模板查找有序数组arr中第一个等于目标值target的位置左边界。def binary_search_left(arr, target): 在升序数组arr中寻找第一个 target 的元素的索引。 如果所有元素都小于target则返回len(arr)。 这可以用来查找target的左边界。 left, right 0, len(arr) # 注意右边界是len(arr)这是一个“左闭右开”区间 [left, right) while left right: # 因为区间是左闭右开所以当leftright时区间为空循环结束 mid left (right - left) // 2 # 防止(leftright)溢出 if arr[mid] target: left mid 1 # 目标在右半部分且mid肯定不是解 else: # arr[mid] target right mid # 目标在左半部分mid有可能是解第一个target的所以保留 return left # 此时leftright且是第一个target的位置 # 查找target是否存在并返回其左边界 def find_target_left(arr, target): idx binary_search_left(arr, target) # 检查找到的位置是否越界以及该位置的值是否等于target if idx len(arr) and arr[idx] target: return idx else: return -1 # 表示未找到2.4.2 查找右边界模板查找有序数组arr中最后一个等于目标值target的位置。def binary_search_right(arr, target): 在升序数组arr中寻找最后一个 target 的元素的索引。 如果所有元素都大于target则返回-1。 这可以用来查找target的右边界。 left, right -1, len(arr) - 1 # 初始化为“左开右闭”区间 (left, right] while left right: # 注意当区间长度为2时(leftright)//2会向下取整到left可能导致死循环。 # 因此需要向上取整。 mid left (right - left 1) // 2 # 关键1确保mid偏向右侧 if arr[mid] target: right mid - 1 # 目标在左半部分mid肯定不是解 else: # arr[mid] target left mid # 目标在右半部分mid有可能是解最后一个target的所以保留 return left # 此时leftright且是最后一个target的位置 def find_target_right(arr, target): idx binary_search_right(arr, target) if idx 0 and arr[idx] target: return idx else: return -1核心技巧二分查找的难点在于mid的取整方式和left/right的更新策略。记住一个原则根据区间的定义来决定如何更新边界。如果区间是[left, right]左闭右闭那么while left right更新时left mid 1或right mid - 1。如果区间是[left, right)左闭右开那么while left right更新时left mid 1或right mid。选择一种并始终坚持可以避免大多数错误。2.5 前缀和与差分区间操作的利器前缀和是一种预处理技术能在O(1)时间内查询数组任意区间的和。差分是其逆运算能高效地对区间进行批量增减操作。2.5.1 一维前缀和def build_prefix_sum(arr): 构建前缀和数组。 prefix[i] 表示 arr[0] arr[1] ... arr[i-1] (前i个元素的和) 通常令 prefix[0] 0这样区间 [l, r] 的和就是 prefix[r1] - prefix[l] n len(arr) prefix [0] * (n 1) for i in range(n): prefix[i 1] prefix[i] arr[i] return prefix def range_sum(prefix, l, r): 查询原数组arr中区间[l, r]的和闭区间 return prefix[r 1] - prefix[l]2.5.2 一维差分差分数组diff满足arr[i] diff[0] diff[1] ... diff[i]。对原数组arr的区间[l, r]统一加上val等价于在差分数组上只修改两个点diff[l] val和diff[r1] - val。def build_diff(arr): 构建差分数组。假设原数组初始全为0经过若干次区间加操作后得到arr。 n len(arr) diff [0] * (n 1) # 多一位方便处理 r1 的边界 # 实际上如果arr是初始数组可以认为它是由对每个位置[i,i]加arr[i]操作得到的。 # 更常见的用法是初始一个全零数组通过差分进行区间操作最后通过前缀和还原。 for i in range(n): # 模拟在区间[i, i]上增加arr[i] diff[i] arr[i] diff[i 1] - arr[i] return diff def apply_diff(initial_arr, diff): 应用差分数组得到操作后的结果数组 n len(initial_arr) result [0] * n current 0 for i in range(n): current diff[i] result[i] initial_arr[i] current return result # 更常用的模式直接进行区间加操作 def range_add_using_diff(diff, l, r, val): 对差分数组diff进行操作表示对原数组区间[l, r]增加val diff[l] val if r 1 len(diff): diff[r 1] - val2.5.3 二维前缀和与差分扩展到二维矩阵原理类似但公式稍复杂。二维前缀和prefix[i][j]表示从(0,0)到(i-1, j-1)的子矩阵和。构建prefix[i][j] matrix[i-1][j-1] prefix[i-1][j] prefix[i][j-1] - prefix[i-1][j-1]查询以(x1,y1)为左上角(x2,y2)为右下角的子矩阵和sum prefix[x21][y21] - prefix[x1][y21] - prefix[x21][y1] prefix[x1][y1]二维差分对子矩阵(x1,y1)到(x2,y2)统一加val等价于在差分矩阵上修改四个点。应用场景前缀和与差分是解决“静态区间求和”和“区间批量更新”问题的标准武器。例如频繁查询数组某个区间的和、计算矩阵中特定子矩阵的元素和、对数组的某个区间所有元素同时加一个数等。在数据量大、操作频繁时能将复杂度从O(n)降至O(1)。3. 模板的整合应用与实战场景掌握了这些独立的模板就像拥有了各种精良的工具。但真正的挑战在于如何根据具体问题灵活地将它们组合起来使用。下面通过几个典型场景来分析。3.1 场景一求解一个大数的所有质因数并计算其约数个数这综合了质因数分解和数论知识。根据算术基本定理一个数N分解为p1^a1 * p2^a2 * ... * pk^ak那么它的正约数个数就是(a11)*(a21)*...*(ak1)。def count_divisors(n): 计算正整数n的正约数个数 factors prime_factorization(n) # 使用前面定义的质因数分解函数 count 1 for _, exp in factors: count * (exp 1) return count # 示例求 100 的约数个数。100 2^2 * 5^2 约数个数 (21)*(21)9 print(count_divisors(100)) # 输出: 93.2 场景二使用二分查找结合前缀和解决问题LeetCode上有一道经典题目“长度最小的子数组”给定一个含有n个正整数的数组和一个正整数target找出该数组中满足其和≥ target的长度最小的连续子数组。 暴力解法是O(n^2)。更优的解法是使用前缀和二分查找复杂度O(n log n)。计算前缀和数组prefix。遍历每个起始位置i我们需要找到最小的j使得prefix[j] - prefix[i] target。这等价于在prefix数组中从i1开始二分查找第一个 prefix[i] target的位置。def min_subarray_len(target, nums): n len(nums) if n 0: return 0 # 构建前缀和 prefix [0] * (n 1) for i in range(n): prefix[i 1] prefix[i] nums[i] min_len float(inf) for i in range(n): sum_to_find prefix[i] target # 在prefix[i1:]中二分查找第一个 sum_to_find 的位置 # 使用自定义的二分查找左边界函数 left, right i 1, n 1 # 在prefix数组的[i1, n]区间查找 while left right: mid left (right - left) // 2 if prefix[mid] sum_to_find: left mid 1 else: right mid j left if j n: # 找到了 min_len min(min_len, j - i) return 0 if min_len float(inf) else min_len当然这道题用滑动窗口可以达到O(n)的线性时间复杂度但“前缀和二分”的思路是一种更通用的范式适用于原数组元素不是正数或者需要查询多次不同target的情况。3.3 场景三高精度运算在组合数学中的应用计算组合数C(n, m)当n和m很大时直接计算阶乘会溢出。可以利用公式C(n, m) n! / (m! * (n-m)!)并结合质因数分解与高精度乘法来避免中间过程的溢出。将分子n!的质因数分解结果与分母m!和(n-m)!的质因数分解结果相减指数相减。将剩余质因数的幂次用高精度乘法乘起来。def factorial_prime_factorization(n): 计算n!的质因数分解返回字典{质数: 指数} # 一种高效方法对于每个质数p计算n!中p的指数为 [n/p] [n/p^2] [n/p^3] ... # 这里为了清晰使用另一种方法对1到n每个数分解质因数然后合并适用于n不太大时 from collections import defaultdict factor_count defaultdict(int) for i in range(2, n 1): factors prime_factorization(i) for p, exp in factors: factor_count[p] exp return factor_count def combination_prime(n, m): 使用质因数分解计算C(n, m) if m n or m 0: return 0 # 计算 n!, m!, (n-m)! 的质因数分解 fact_n factorial_prime_factorization(n) fact_m factorial_prime_factorization(m) fact_nm factorial_prime_factorization(n - m) # 合并结果: C(n,m) n! / (m! * (n-m)!) result_factors {} for p in fact_n: exp fact_n[p] - fact_m.get(p, 0) - fact_nm.get(p, 0) if exp 0: result_factors[p] exp # 将质因数表示的高精度数乘起来 result 1 for p, exp in result_factors.items(): # 计算 p^exp 用快速幂思想结合高精度乘法 power_str str(p) # 快速幂计算 p^exp e exp while e 0: if e % 2 1: result high_precision_mul_big_small(result, int(power_str)) power_str high_precision_mul_big_small(power_str, int(power_str)) # 平方 e // 2 return result这种方法虽然代码稍长但能精确计算非常大的组合数是处理大数组合问题的可靠方法。4. 常见问题、调试技巧与性能优化即使有了模板在实际编码和调试中还是会遇到各种问题。下面分享一些我积累的经验和常见陷阱。4.1 素数筛法中的典型错误数组大小错误埃筛或线性筛的数组通常需要开到n1或n用于表示数字0到n-1或1到n。务必明确下标与数字的对应关系否则会导致数组越界或漏判。循环边界不清埃筛的外层循环for i in range(2, int(n**0.5)1)必须是 sqrt(n)。内层循环for j in range(i*i, n, i)的起始点i*i是优化要理解其原理。线性筛的if i % p 0: break这是保证线性的关键务必牢记。它确保了每个合数i*p只被其最小质因子p筛掉。4.2 二分查找的“死循环”与边界错误这是二分查找的重灾区。死循环通常发生在while left right且更新策略为left mid或right mid时。如果计算mid是向下取整(leftright)//2当left和right相差1时mid会等于left。如果此时分支走向是left mid那么区间将不会缩小导致死循环。解决方案在需要保留mid的情况下让mid向上取整(leftright1)//2。找不到元素检查循环结束后left或right指向的位置是否有效在数组范围内以及该位置的值是否等于目标值。通用调试技巧在循环内打印left,right,mid的值以及arr[mid]与target的比较结果这是理解二分过程最直观的方法。对于复杂问题可以先用小规模数据手动模拟。4.3 高精度运算的细节陷阱前导零处理在完成加法、乘法运算后反转回来的字符串可能有多余的前导零如000123。必须使用.lstrip(0)去除但要小心结果本身就是0的情况去除后会变成空字符串需要特殊处理if sum_str else 0。进位/借位的最终处理在循环结束后一定要检查最后的carry或borrow是否为非零并妥善处理。符号处理减法必须考虑正负。一个稳健的实现是先比较两个绝对值大小决定结果符号然后用大绝对值减去小绝对值。性能优化对于极长数字的乘法Python内置的int类型已经高度优化通常比自己实现的高精度字符串算法快得多。只有在教学或特定限制如其他语言下才需要手动实现。但在C中手写高精度是常态。4.4 前缀和与差分的索引偏移这是最容易出错的地方。为了让公式统一区间[l, r]的和等于prefix[r1] - prefix[l]我们通常定义prefix[0] 0prefix[i]表示前i个元素的和下标从0到i-1。务必在脑海中明确prefix数组的下标含义。画图是理清关系的最好方法。4.5 性能考量与工具选择素数判定对于单个大数的素数判定除了试除法还有Miller-Rabin概率素性测试速度更快适用于极大数如密码学领域。GCD计算Python的math.gcd是用C实现的效率极高绝对优于任何手写Python版本。多个数的GCD/LCM使用functools.reduce配合math.gcd/lcm函数非常优雅。import math, functools nums [12, 18, 24] gcd_val functools.reduce(math.gcd, nums) lcm_val functools.reduce(lambda x, y: x // math.gcd(x, y) * y, nums)二分查找Python的bisect模块提供了现成的二分查找函数bisect_left,bisect_right其实现经过优化且无bug在允许使用标准库时应作为首选。高精度运算如前所述在Python中除非有特殊限制如模拟算法过程否则直接使用int类型。需要处理浮点数高精度时可以考虑decimal模块。把这些基础模板练到肌肉记忆里理解其每一个细节和变体在遇到复杂问题时你就能像搭积木一样快速组合出解决方案。编程竞赛和工程中的很多难题拆解到底层往往就是这些基础算法的巧妙结合。这份总结不是终点而是一个随时可以回来查阅、修正和补充的起点。在实际编码中最宝贵的经验往往来自于调试那些因为一个等号、一个边界条件而浪费的几个小时希望我的这些踩坑记录能帮你绕过一些弯路。