数据结构与算法自学笔记（18）- 最大公约数、同余原理与对数器打表规律

引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series

本笔记内容囊括class41-class42，class41讲的是数学基础中的最大公约数、最小公倍数计算，以及同余原理的应用。此外class42讲了对数器打表找规律的技巧，通过暴力解小规模数据，观察输出规律，最终得到高效的数学解法。

重要说明

这两个内容都和数学比较相关，所以放在了一起。同余原理等等都是抽象代数的基本操作，对数器打表则需要我们观察数学规律，然后再高效求解。

---

041【必备】最大公约数、同余原理

前置知识

在学习本内容之前，需要掌握以下基础知识：

• 基本的数学运算
• 递归的概念
• 二分查找的基本思想

重要说明

• 本期内容涵盖欧几里得算法（辗转相除法）的原理与实现
• 同余原理在防止大数溢出方面的应用
• 二分答案法与容斥原理的简单应用
• 更高效的Stein算法和裴蜀定理会在后续扩展课程中讲述

核心知识点一：最大公约数与最小公倍数

欧几里得算法（辗转相除法）

算法原理

辗转相除法的核心是证明以下关系：
$$\gcd(a, b) = \gcd(b, a \bmod b)$$

其中 $a \bmod b$ 表示 $a$ 除以 $b$ 的余数。

正确性证明

设 $a \bmod b = r$，即需要证明：$\gcd(a, b) = \gcd(b, r)$

证明过程：

1. 由 $a \bmod b = r$ 可得：

   • $a = b \times q + r$（其中 $q$ 为商）
   • $r = a - b \times q$

2. 设 $u$ 是 $a$ 和 $b$ 的公因子，则有：$a = s \times u$，$b = t \times u$

3. 将上式代入得：$r = s \times u - t \times u \times q = (s - t \times q) \times u$

4. 这说明：$u$ 如果是 $a$ 和 $b$ 的公因子，那么 $u$ 也是 $r$ 的因子

5. 反之，设 $v$ 是 $b$ 和 $r$ 的公因子，则有：$b = x \times v$，$r = y \times v$

6. 代入得：$a = x \times v \times q + y \times v = (x \times q + y) \times v$

7. 这说明：$v$ 如果是 $b$ 和 $r$ 的公因子，那么 $v$ 也是 $a$ 的公因子

结论： $a$ 和 $b$ 的全体公因子集合 = $b$ 和 $r$ 的全体公因子集合，因此 $\gcd(a, b) = \gcd(b, r)$

算法实现

class MathUtils:
    def gcd(self, a: int, b: int) -> int:
        """
        使用辗转相除法（欧几里得算法）计算最大公约数。
        核心思想：
        两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。
        递归的基准情况是当 b 为 0 时，最大公约数是 a。
        """
        return a if b == 0 else self.gcd(b, a % b)

    def lcm(self, a: int, b: int) -> int:
        """
        计算最小公倍数。
        核心思想：
        两个数的最小公倍数可以通过公式 `(a * b) / gcd(a, b)` 计算得出。
        为了防止 `a * b` 在某些语言中溢出，可以写成 `a / gcd(a, b) * b`。
        在 Python 中，整数支持任意精度，不存在溢出问题，但这种写法仍然是好习惯。
        """
        # 使用 // 保证整数除法
        return (a // self.gcd(a, b)) * b

算法分析

• 时间复杂度：$O((\log a)^3)$，其中 $a > b$
• 空间复杂度：$O(\log a)$（递归调用栈）
• 核心优势：算法简洁，效率高，易于实现

使用示例

utils = MathUtils()
a, b = 48, 18
print(f"GCD of {a} and {b} is: {utils.gcd(a, b)}")  # 输出: 6
print(f"LCM of {a} and {b} is: {utils.lcm(a, b)}")  # 输出: 144

---

核心知识点二：神奇数问题（二分答案法 + 容斥原理）

问题描述

一个正整数如果能被 $a$ 或 $b$ 整除，那么它是神奇的。给定三个整数 $n$, $a$, $b$，返回第 $n$ 个神奇的数字。因为答案可能很大，所以返回答案对 $10^9 + 7$ 取模后的值。

测试链接：https://leetcode.cn/problems/nth-magical-number/

核心思想

这个问题巧妙地结合了两个重要算法：

1. 二分答案法：答案具有单调性，可以二分查找
2. 容斥原理：计算能被 $a$ 或 $b$ 整除的数的个数

二分答案法分析

对于任意数字 $m$，小于等于 $m$ 的神奇数字个数具有单调性：$m$ 越大，神奇数字越多。因此可以二分查找第 $n$ 个神奇数字。

容斥原理应用

计算 $1$ 到 $m$ 中能被 $a$ 或 $b$ 整除的数的个数：

$$\text{count} = \lfloor\frac{m}{a}\rfloor + \lfloor\frac{m}{b}\rfloor - \lfloor\frac{m}{\text{lcm}(a,b)}\rfloor$$

其中减去 $\lfloor\frac{m}{\text{lcm}(a,b)}\rfloor$ 是因为被 $a$ 和 $b$ 同时整除的数被重复计算了。

算法实现

class Solution:
    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
        """
        寻找第 n 个神奇数字。
        核心思想：
        答案本身具有单调性（越大的数，它前面的神奇数字越多），因此可以使用二分查找来寻找答案。
        1. 定义查找范围：下界 `l=0`，上界 `r` 可以是一个足够大的数，例如 `n * min(a, b)`。
        2. 二分中点为 `m`，我们需要快速计算出 `1` 到 `m` 之间有多少个神奇数字。
        3. 这个数量可以通过容斥原理计算：`count = m/a + m/b - m/lcm(a, b)`。
           其中 `lcm` 是 a 和 b 的最小公倍数。
        4. 如果 `count >= n`，说明第 `n` 个神奇数字可能就是 `m` 或者更小，所以我们将 `m` 存为候选答案，并向左查找 `r = m - 1`。
        5. 如果 `count < n`，说明 `m` 太小了，第 `n` 个神奇数字在 `m` 的右边，所以向右查找 `l = m + 1`。
        6. 二分结束后，候选答案即为所求，最后对结果取模。
        """
        lcm_val = self._lcm(a, b)
        ans = 0
        mod = 1000000007
        
        # l = 0, r = n * min(a, b) 是一个安全上界
        l, r = 0, n * min(a, b)
        
        while l <= r:
            m = (l + r) // 2
            # 计算 1...m 中有多少个数是 a 或 b 的倍数
            # 使用容斥原理：(m中a的倍数) + (m中b的倍数) - (m中a和b公倍数的个数)
            if m // a + m // b - m // lcm_val >= n:
                ans = m
                r = m - 1
            else:
                l = m + 1
                
        return ans % mod

    def _gcd(self, a: int, b: int) -> int:
        return a if b == 0 else self._gcd(b, a % b)

    def _lcm(self, a: int, b: int) -> int:
        return (a * b) // self._gcd(a, b)

算法分析

• 时间复杂度：$O(\log(\text{n} \times \min(a, b)))$
• 空间复杂度：$O(\log(\min(a, b)))$（递归调用栈）
• 核心技巧：二分答案法 + 容斥原理

---

核心知识点三：同余原理

基本公理

设 $m$ 为正整数（模），若：

• $a \equiv b \pmod{m}$
• $c \equiv d \pmod{m}$

则有：

• 加法：$a + c \equiv b + d \pmod{m}$
• 减法：$a - c \equiv b - d \pmod{m}$
• 乘法：$ac \equiv bd \pmod{m}$

核心思想

在模运算中，我们可以在每一步计算后都取模，这样可以：

1. 防止中间结果溢出
2. 保持计算结果的正确性
3. 提高计算效率

实际应用

问题：计算 $((a + b) \times (c - d) + (a \times c - b \times d)) \bmod m$

class Solution:
    def f1(self, a: int, b: int, c: int, d: int, mod: int) -> int:
        """
        使用 Python 的原生大整数计算，等同于 Java 的 BigInteger 版本。
        核心思想：
        直接进行数学运算，让语言自动处理中间过程中可能出现的巨大数值。
        最后对最终结果取模。
        """
        o5 = a + b
        o6 = c - d
        o7 = a * c
        o8 = b * d
        o9 = o5 * o6
        o10 = o7 - o8
        o11 = o9 + o10
        # (res % mod + mod) % mod 是一个确保结果为正的通用技巧。
        return (o11 % mod + mod) % mod

    def f2(self, a: int, b: int, c: int, d: int, mod: int) -> int:
        """
        使用同余原理在每一步运算后都取模。
        核心思想 (同余原理)：
        - (A + B) % M = ((A % M) + (B % M)) % M
        - (A - B) % M = ((A % M) - (B % M) + M) % M  (加上M确保结果非负)
        - (A * B) % M = ((A % M) * (B % M)) % M
        这种方法可以保证所有中间计算结果都在一个可控的范围内，避免大数运算，效率更高。
        """
        o1 = a % mod
        o2 = b % mod
        o3 = c % mod
        o4 = d % mod
        o5 = (o1 + o2) % mod
        # 加上 mod 再取模，是为了防止 o3 < o4 时出现负数
        o6 = (o3 - o4 + mod) % mod
        o7 = (o1 * o3) % mod
        o8 = (o2 * o4) % mod
        o9 = (o5 * o6) % mod
        o10 = (o7 - o8 + mod) % mod
        ans = (o9 + o10) % mod
        return ans

重要注意事项

1. 减法处理：$(a - b) \bmod m = ((a \bmod m) - (b \bmod m) + m) \bmod m$

   • 加上 $m$ 是为了确保结果非负

2. 除法同余：需要求逆元，比较复杂，会在后续课程中讲述

3. 数据类型：在需要防止溢出的语言中，乘法运算常用长整型做中间变量

验证代码

import random
import sys

def random_long():
    return random.randint(0, sys.maxsize)

if __name__ == '__main__':
    s = Solution()
    print("测试开始")
    test_time = 100000
    mod = 1000000007
    all_passed = True
    
    for i in range(test_time):
        a = random_long()
        b = random_long()
        c = random_long()
        d = random_long()
        if s.f1(a, b, c, d, mod) != s.f2(a, b, c, d, mod):
            print("出错了!")
            all_passed = False
            break
    
    if all_passed:
        print("测试结束，全部通过!")

---

算法技巧总结

1. 欧几里得算法模板

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

def lcm(a, b):
    return (a * b) // gcd(a, b)

2. 二分答案法模板

def binary_search_answer(check_function, left, right):
    ans = -1
    while left <= right:
        mid = (left + right) // 2
        if check_function(mid):
            ans = mid
            right = mid - 1  # 继续寻找更小的答案
        else:
            left = mid + 1
    return ans

3. 容斥原理（两个集合）

# |A ∪ B| = |A| + |B| - |A ∩ B|
def inclusion_exclusion_two_sets(n, a, b):
    lcm_ab = lcm(a, b)
    return n // a + n // b - n // lcm_ab

4. 同余运算模板

def safe_mod_operations(a, b, mod):
    # 加法
    add_result = (a + b) % mod
    
    # 减法（确保非负）
    sub_result = (a - b + mod) % mod
    
    # 乘法
    mul_result = (a * b) % mod
    
    return add_result, sub_result, mul_result

---

复杂度分析总结

算法	时间复杂度	空间复杂度	应用场景
欧几里得算法	$O(\log \min(a,b))$	$O(\log \min(a,b))$	求最大公约数
神奇数问题	$O(\log(n \times \min(a,b)))$	$O(\log \min(a,b))$	二分答案法
同余运算	$O(1)$	$O(1)$	防止溢出

---

学习建议

1. 掌握数学基础

• 理解最大公约数和最小公倍数的定义
• 掌握同余的概念和性质
• 熟悉容斥原理的基本应用

2. 算法思维训练

• 二分答案法：当答案具有单调性时考虑使用
• 容斥原理：处理集合交并关系的重要工具
• 同余优化：在模运算中防止溢出的关键技巧

3. 实践要点

• 欧几里得算法是最基础的数学算法，必须熟练掌握
• 同余原理在竞赛和工程中都很重要，特别是处理大数时
• 二分答案法是一种重要的算法思想，适用范围很广

4. 扩展学习

• Stein算法：更高效的最大公约数算法
• 裴蜀定理：关于线性丢番图方程的重要定理
• 扩展欧几里得算法：求解模逆元的基础
• 中国剩余定理：处理多个同余方程组

5. 注意事项

• 在实现递归版本时注意栈溢出问题
• 处理负数时要特别小心同余运算
• 在竞赛中，往往需要对结果取模，要养成习惯

通过掌握这些数学基础知识和算法技巧，可以为解决更复杂的数学相关算法问题打下坚实的基础。这些知识点不仅在算法竞赛中经常出现，在实际工程开发中也有重要应用价值。

042【必备】对数器打表找规律的技巧

前置知识

在学习本内容之前，需要掌握以下基础知识：

• 基本递归能力（推荐讲解038-常见经典递归过程解析）
• 动态规划的基本思想
• 博弈论的基础概念

使用场景

对数器打表找规律适用于：

• 输入参数是简单类型
• 返回值也是简单类型
• 暴力解法可以处理小规模数据
• 存在数学规律可以发现

方法论

1. 暴力实现：用最基本的递归实现求解小规模问题
2. 打表观察：打印小规模输入的答案，寻找规律
3. 规律验证：将观察到的规律转换为代码并验证
4. 优化实现：基于规律得到最优解

问题一：使用规格8和规格6的袋子买苹果

问题描述

有装下8个苹果的袋子、装下6个苹果的袋子，一定要保证买苹果时所有使用的袋子都装满。对于无法装满所有袋子的方案不予考虑，给定n个苹果，返回至少要多少个袋子。如果不存在每个袋子都装满的方案返回-1。

核心思想

这是一个典型的整数规划问题，可以用动态规划或递归求解，也可以通过观察规律得到数学解法。

方法一：暴力递归（备忘录优化）

import math

class Solution:
    def bags1(self, apple: int) -> int:
        """
        主函数，调用递归并处理无效解的返回值
        """
        # 使用 memoization (备忘录) 来优化递归，避免重复计算
        memo = {}
        ans = self._f(apple, memo)
        # 如果返回的是无穷大，说明无解，返回-1
        return ans if ans != math.inf else -1

    def _f(self, rest: int, memo: dict) -> int:
        """
        递归函数，计算装下 rest 个苹果所需的最少袋子数
        核心思想 (回溯/动态规划)：
        对于 `rest` 个苹果，我们有两种选择：
        1. 用一个8个装的袋子，问题变为求解 `f(rest - 8)`。
        2. 用一个6个装的袋子，问题变为求解 `f(rest - 6)`。
        我们需要在这两种选择中，选择总袋子数最少的那一个。
        """
        if rest in memo: # 如果之前已经算过当前 rest（还剩多少苹果）对应的最少袋子数
            return memo[rest] 
        
        # base case: 苹果数小于0，说明上一步的选择是无效的
        if rest < 0:
            return math.inf
        
        # base case: 苹果数为0，说明刚好装完，不再需要袋子
        if rest == 0:
            return 0
        
        # 尝试用一个8规格的袋子
        p1 = self._f(rest - 8, memo)
        # 尝试用一个6规格的袋子
        p2 = self._f(rest - 6, memo)
        
        # 在有效解的基础上加1 (代表当前用的这个袋子)
        res = min(p1, p2) + 1
        
        memo[rest] = res
        return res

方法二：规律观察优化解

通过打表观察发现规律：

def bags2(self, apple: int) -> int:
    """
    通过暴力解的输出观察规律，得到的数学优化方法
    核心思想：
    - 苹果数必须是偶数，因为袋子规格6和8都是偶数。
    - 观察小数据量的解，发现 apple < 18 时情况比较特殊，可以直接列出。
    - 当 apple >= 18 时，规律出现。为了用最少的袋子，应尽可能多地使用8个装的袋子。
      可以证明任何 >= 18 的偶数 `apple` 都可以表示为 `8*k + c` 的形式，
      其中 `c` 是一个可以用6和8凑出来的小数（比如18, 20, 22）。
      `apple - 18` 的部分全部用8个装的袋子，剩下的18个苹果用3个6个装的袋子。
    """
    # base case:如果苹果数是奇数，无解
    if (apple & 1) != 0:
        return -1
    
    # base case:处理18以下的特殊情况
    if apple < 18:
        if apple == 0:
            return 0
        if apple == 6 or apple == 8:
            return 1
        if apple == 12 or apple == 14 or apple == 16:
            return 2
        return -1
    
    # 处理18及以上的情况
    # (apple - 18) 用8个装的袋子，18用3个6个装的袋子
    return (apple - 18) // 8 + 3

规律分析

通过打表观察，我们发现：

苹果数 : 最少袋子数
0 : 0
1 : -1 (奇数无解)
2 : -1
3 : -1 (奇数无解)
4 : -1
5 : -1 (奇数无解)
6 : 1    (1个6袋)
7 : -1 (奇数无解)
8 : 1    (1个8袋)
9 : -1 (奇数无解)
10 : -1
11 : -1 (奇数无解)
12 : 2   (2个6袋)
13 : -1 (奇数无解)
14 : 2   (1个6袋+1个8袋)
15 : -1 (奇数无解)
16 : 2   (2个8袋)
17 : -1 (奇数无解)
18 : 3   (3个6袋)
20 : 3   (1个6袋+1个8袋+1个6袋 或 其他组合)
22 : 3   (1个6袋+2个8袋)
24 : 3   (3个8袋)
...

规律：当 apple >= 18 且为偶数时，答案为 (apple - 18) // 8 + 3

算法分析

• 暴力递归：时间复杂度 O(N)，空间复杂度 O(N)
• 规律优化：时间复杂度 O(1)，空间复杂度 O(1)

---

问题二：A和B轮流吃草博弈问题

问题描述

草一共有n的重量，两只牛轮流吃草，A牛先吃，B牛后吃。每只牛在自己的回合，吃草的重量必须是4的幂，1、4、16、64…。谁在自己的回合正好把草吃完谁赢，根据输入的n，返回谁赢。

核心思想

这是一个典型的博弈论问题，使用Min-Max算法求解。关键在于理解必胜态和必败态的概念。

方法一：暴力递归（博弈论）

class Solution:
    def win1(self, n: int) -> str:
        """
        主函数，启动递归
        """
        # 使用 memoization 优化
        memo = {}
        return self._f(n, "A", memo)

    def _f(self, rest: int, cur: str, memo: dict) -> str:
        """
        递归函数，模拟博弈过程
        核心思想 (博弈论 Min-Max 思想):
        - `cur` (当前玩家)能赢的条件是：`cur` 存在一种走法，使得走完后，`enemy` (对手)面对的局面是必败的。
        - 必败态：无论怎么走，留给对手的都是必胜态。
        - 必胜态：存在一种走法，留给对手的是必败态。
        - 我们遍历当前玩家所有可能的吃草量 (4的幂)，如果吃完后留给对手的局面是对手必败（即当前玩家赢），
          那么当前局面就是必胜态，`cur` 赢。
        - 如果所有走法都无法让对手输，那么 `cur` 输。
        """
        if (rest, cur) in memo:
            return memo[(rest, cur)]

        enemy = "B" if cur == "A" else "A"
        
        # base case: 剩草小于5时，可以直接判断胜负
        if rest < 5:
            # 剩0或2时，当前玩家没法一步吃完，所以对手赢
            # 剩1,3,4时，当前玩家可以一步吃完，所以当前玩家赢
            winner = enemy if (rest == 0 or rest == 2) else cur
            memo[(rest, cur)] = winner
            return winner
        
        # rest >= 5
        # 遍历所有可能的吃草量
        pick = 1
        while pick <= rest:
            # `_f(rest - pick, enemy)` 返回的是：当剩下 `rest-pick` 的草，轮到 `enemy` 时，最终谁会赢。
            # 如果这个结果是 `cur` 赢，说明 `cur` 只要选择吃 `pick` 的草，就能锁定胜局。
            if self._f(rest - pick, enemy, memo) == cur:
                memo[(rest, cur)] = cur
                return cur
            
            # 防止 pick * 4 溢出 (在 Python 中不是问题，但在某些语言中需要注意)
            if pick > rest // 4: #先算//，再与pick比较
                break
            pick *= 4
        
        # 如果所有可能的走法都无法让 cur 赢，那么 enemy 赢
        memo[(rest, cur)] = enemy
        return enemy

方法二：规律观察优化解

通过打表发现胜负规律：

def win2(self, n: int) -> str:
    """
    通过暴力解的输出，发现胜负结果以5为周期循环
    核心思想：
    观察 `win1` 的输出，可以发现：
    n=0 -> B (先手输)
    n=1 -> A (先手赢)
    n=2 -> B (先手输)
    n=3 -> A (先手赢)
    n=4 -> A (先手赢)
    n=5 -> B (先手输)
    ...
    胜负状态是 (B, A, B, A, A)，以5为周期。
    当 n % 5 的结果是 0 或 2 时，先手方 A 面对的是必败局面，所以 B 赢。
    否则 A 赢。
    """
    if n % 5 == 0 or n % 5 == 2:
        return "B"
    else:
        return "A"

规律分析

通过打表观察：

草量 : 赢家
0 : B
1 : A
2 : B
3 : A
4 : A
5 : B
6 : A
7 : B
8 : A
9 : A
10 : B
...

发现模式：(B, A, B, A, A) 以5为周期重复。

算法分析

• 暴力递归：时间复杂度 O(N×logN)，空间复杂度 O(N)
• 规律优化：时间复杂度 O(1)，空间复杂度 O(1)

---

问题三：判断连续正整数和

问题描述

判断一个数字是否是若干数量(数量>1)的连续正整数的和。

核心思想

这是一个数论问题，可以通过数学推导得到简洁的判断条件。

方法一：暴力枚举

class Solution:
    def is1(self, num: int) -> bool:
        """
        暴力尝试所有可能的连续正整数序列
        核心思想：
        - 从 1 开始，尝试每一个数 `start` 作为连续序列的起始点。
        - 对于每一个 `start`，累加 `start, start+1, start+2, ...`
        - 如果累加和等于 `num`，则找到了一个解，返回 True。
        - 如果累加和大于 `num`，则以 `start` 为起点的序列不可能，跳出内层循环。
        """
        # start 是连续区间的开始
        for start in range(1, num + 1):
            current_sum = start
            # 从 start+1 开始累加
            for j in range(start + 1, num + 1):
                if current_sum + j > num:
                    # 累加和已超，后续不可能相等
                    break
                if current_sum + j == num:
                    # 找到了一个解
                    return True
                current_sum += j
        return False

方法二：数学规律

def is2(self, num: int) -> bool:
    """
    通过数学推导得出的结论
    核心思想：
    一个正整数 `num` 可以表示为连续k(k>1)个正整数之和的充要条件是：`num` 不是2的幂。
    证明：
    1. 设 `num = a + (a+1) + ... + (a+k-1) = k*a + k*(k-1)/2`
    2. `2*num = k*(2a + k - 1)`
    3. `k` 和 `2a+k-1` 中一个是奇数，一个是偶数。
    4. 如果 `num` 是2的幂，`num = 2^p`，那么 `2*num = 2^(p+1)`。
       `2^(p+1)` 的所有因子都是2的幂（偶数），无法分解成一奇一偶的乘积
       （除了 1*2^(p+1)，但这要求 k=1 或 2a+k-1=1，都与 k>1, a>=1 矛盾）。
    5. 所以，如果 `num` 是2的幂，则无解。反之，如果 `num` 不是2的幂，则 `num` 必有奇数因子，可以构造出解。
    
    判断一个数是否是2的幂，可以通过位运算 `num & (num - 1) == 0` 来实现。
    这是因为num的二进制表示只有一个1，所以num-1的二进制表示只有一个0，所以num & (num - 1) == 0。
    所以，判断一个数不是2的幂，就是 `(num & (num - 1)) != 0`。
    """
    if num < 3: # 1和2不满足条件
        return False
    # 如果一个数是2的幂，它的二进制表示中只有一个1
    # num & (num - 1) 的作用是消除最右边的1。
    # 如果结果为0，说明num只有一个1，是2的幂。
    # 如果结果不为0，说明num不是2的幂。
    return (num & (num - 1)) != 0

数学推导详解

对于连续k个正整数的和：
$$\text{sum} = a + (a+1) + \ldots + (a+k-1) = ka + \frac{k(k-1)}{2}$$

整理得：
$$2 \times \text{sum} = k(2a + k - 1)$$

这说明 $2 \times \text{sum}$ 可以分解为两个因子的乘积，且一个是奇数，一个是偶数。

如果 $\text{sum} = 2^p$，则 $2 \times \text{sum} = 2^{p+1}$，所有因子都是偶数，无法满足一奇一偶的要求。

算法分析

• 暴力枚举：时间复杂度 O(N²)，空间复杂度 O(1)
• 数学规律：时间复杂度 O(1)，空间复杂度 O(1)

---

问题四：RED字符串好串计数

问题描述

可以用r、e、d三种字符拼接字符串，如果拼出来的字符串中有且仅有1个长度>=2的回文子串，那么这个字符串定义为”好串”。返回长度为n的所有可能的字符串中，好串有多少个。结果对 1000000007 取模，1 <= n <= 10^9。

核心思想

这是一个组合数学问题，通过暴力递归生成所有可能的字符串并检验，然后观察规律。

方法一：暴力递归

class Solution:
    def num1(self, n: int) -> int:
        """
        主函数，启动暴力递归生成所有字符串并检查
        """
        path = [''] * n
        return self._f(path, 0)

    def _f(self, path: list, i: int) -> int:
        """
        递归函数，生成所有长度为n的字符串
        """
        if i == len(path): #这就是base case
            # 字符串生成完毕，检查是否为"好串"
            cnt = 0
            # 遍历所有长度>=2的子串
            for l in range(len(path)):
                for r in range(l + 1, len(path)):
                    if self._is_palindrome(path, l, r):
                        cnt += 1
                    if cnt > 1:
                        # 超过1个回文子串，直接判定为非好串
                        return 0
            # 最终检查回文子串数量是否正好为1
            return 1 if cnt == 1 else 0
        else:
            # 在 i 位置尝试 'r', 'e', 'd' 三种字符
            ans = 0
            path[i] = 'r'
            ans += self._f(path, i + 1)
            path[i] = 'e'
            ans += self._f(path, i + 1)
            path[i] = 'd'
            ans += self._f(path, i + 1)
            return ans

    def _is_palindrome(self, s: list, l: int, r: int) -> bool:
        """
        辅助函数，检查子串是否为回文
        """
        while l < r:
            if s[l] != s[r]:
                return False
            l += 1
            r -= 1
        return True

方法二：规律观察

def num2(self, n: int) -> int:
    """
    通过暴力解的结果，发现数学规律
    核心思想：
    运行 `num1` 得到：
    n=1: 0
    n=2: 3   (rr, ee, dd)
    n=3: 18  (rre, rrd, rer, der, ...)
    n=4: 30
    n=5: 36
    ...
    可以发现规律：
    n=1 -> 0
    n=2 -> 3
    n=3 -> 18
    n>3 -> ans(n-1) + 6，即为一个等差数列，通项公式为 `18 + (n-3)*6 = 6*n`。
    但题目中的答案是 `6*(n+1)`，我们来验证
    n=4: 6*(4+1)=30.
    n=5: 6*(5+1)=36.
    这个规律是正确的。所以可以直接用公式计算。
    """
    mod = 1000000007
    if n == 1:
        return 0
    if n == 2:
        return 3
    if n == 3:
        return 18
    # (6 * (n + 1)) % mod
    return (6 * (n + 1)) % mod

规律分析

通过打表观察：

长度 : 好串数量
1 : 0    (无法构成长度>=2的回文)
2 : 3    (rr, ee, dd)
3 : 18   
4 : 30   = 6×(4+1)
5 : 36   = 6×(5+1)
6 : 42   = 6×(6+1)
...

发现规律：

• n=1: 0
• n=2: 3
• n=3: 18
• n≥4: 6×(n+1)

算法分析

• 暴力递归：时间复杂度 O(3^N × N³)，空间复杂度 O(N)
• 规律优化：时间复杂度 O(1)，空间复杂度 O(1)

---

核心技巧总结

1. 对数器打表的通用流程

def solve_by_pattern_finding(n):
    """对数器打表找规律的标准流程"""
    
    # 步骤1: 实现暴力解法
    def brute_force_solution(n):
        # 用最基本的递归或暴力方法实现
        pass
    
    # 步骤2: 打表观察规律
    print("输入 : 输出")
    for i in range(small_range):
        result = brute_force_solution(i)
        print(f"{i} : {result}")
    
    # 步骤3: 根据观察到的规律实现优化解
    def optimized_solution(n):
        # 基于规律的O(1)或低复杂度解法
        pass
    
    return optimized_solution(n)

2. 递归 + 记忆化模板

def recursive_with_memo(params):
    memo = {}
    
    def helper(state):
        if state in memo:
            return memo[state]
        
        # base case
        if is_base_case(state):
            return base_result
        
        # 递归计算
        result = calculate_from_subproblems(state)
        memo[state] = result
        return result
    
    return helper(initial_state)

3. 博弈论问题模板

def game_theory_solution(state, current_player):
    memo = {}
    
    def can_win(state, player):
        if (state, player) in memo:
            return memo[(state, player)]
        
        # base case
        if is_terminal_state(state):
            return determine_winner(state, player)
        
        # 尝试所有可能的移动
        for move in get_possible_moves(state):
            new_state = apply_move(state, move)
            opponent = get_opponent(player)
            
            # 如果存在一步移动使得对手必败，当前玩家必胜
            if can_win(new_state, opponent) == player:
                memo[(state, player)] = player
                return player
        
        # 所有移动都无法获胜，当前玩家必败
        opponent = get_opponent(player)
        memo[(state, player)] = opponent
        return opponent
    
    return can_win(state, current_player)

4. 位运算判断2的幂

def is_power_of_two(n):
    """判断n是否为2的幂"""
    return n > 0 and (n & (n - 1)) == 0

def is_not_power_of_two(n):
    """判断n是否不是2的幂"""
    return n > 0 and (n & (n - 1)) != 0

---

复杂度分析总结

问题类型	暴力解复杂度	优化解复杂度	核心技巧
苹果袋子问题	O(N)	O(1)	动态规划→数学规律
吃草博弈	O(N×logN)	O(1)	博弈论→周期性规律
连续正整数和	O(N²)	O(1)	数论→2的幂判断
好串计数	O(3^N×N³)	O(1)	穷举打表→发现数学规律

---

学习建议

1. 掌握基础技能

• 递归思维：熟练掌握递归的设计和实现
• 动态规划：理解状态转移和最优子结构
• 博弈论基础：了解必胜态和必败态的概念
• 数学基础：具备基本的数论和组合数学知识

2. 培养观察能力

• 模式识别：善于从数据中发现周期性、递推性等规律
• 数学直觉：能够将观察到的规律转化为数学公式
• 验证习惯：发现规律后及时验证其正确性

3. 实践要点

• 小数据打表：从小规模数据开始，逐步观察规律
• 多角度思考：尝试不同的观察角度和数学工具
• 渐进优化：从暴力解→记忆化→数学公式的渐进优化过程

4. 常见规律类型

• 周期性规律：如博弈问题中的周期性胜负模式
• 递推关系：如斐波那契数列、等差数列等
• 数学性质：如2的幂的位运算性质
• 组合规律：如排列组合中的计数问题

5. 注意事项

• 边界条件：特别注意小数据的边界情况
• 数据范围：考虑大数据下的溢出和效率问题
• 规律验证：确保发现的规律在所有情况下都成立
• 代码实现：将数学规律正确转化为代码逻辑

通过掌握对数器打表找规律的技巧，可以将许多看似复杂的问题转化为简单的数学计算，大幅提升算法效率。这种方法在算法竞赛和实际工程中都有重要应用价值。