Advent of Code 2025 - 第2天题解

核心任务描述

给定一个数字范围，找出范围中所有由一个完全相同的数字片段重复若干次拼接而成的数字。其中，第一部分要求仅需找出由两个相同片段组成的数字，第二部分则要求找出由任意数量（不少于两个）相同片段组成的数字。

数字	是否符合要求（第一部分）	是否符合要求（第二部分）	说明
123123			由两个 “123” 组成
121212			由三个 “12” 组成
1234			无重复片段组成
1111			可看作由两个 “11” 或四个 “1” 组成

思考过程

字符串判断

题目本身并不难，最简单的思路就是使用字符串操作来判断一个数字是否由重复片段组成。具体来说：

将数字转换为字符串形式 s。
遍历可能的片段长度 k，范围从 1 到 s.len() / 2。
对于每个片段长度，检查字符串是否可以被该长度整除。
如果可以整除，则提取第一个片段 part = &s[0..k]，并检查 s 是否等于 part 重复若干次的结果。
如果找到了符合条件的片段，则该数字符合要求。

这种方法虽然简单直观，但时间复杂度较高，尤其是在数字范围较大时，效率不佳。

数学方法

我们从第一部分的要求出发，考虑如何通过数学方法来判断一个数字是否由两个相同片段组成。

比如数字 123123，我们可以将其表示为：

\begin{aligned} 123123 = & 123 \times 10^3 + 123 \\ = & 123 \times (10^3 + 1) \\ = & 123 \times 1001 \end{aligned}

不难发现，对于任何长度为偶数的数字，如果它由两个相同的 $k$ 位片段组成，那么它一定可以写成 $part \times (10^{k} + 1)$ 的形式，其中 $k$ 是 $part$ 的长度。我们可以将 $10^{k} + 1$ 记为 $base$ ，那么问题就转化为了判断一个数字 $x$ 是否可以被 $base$ 整除。

基于上述分析，我们可以设计如下算法：

对于长度为偶数的数字 $x$ ，计算其长度 $L$ 。
计算 $k = L / 2$ ，并计算 $base = 10^{k} + 1$ 。
检查 $x$ 是否可以被 $base$ 整除。
如果满足上述条件，则 $x$ 符合要求。

这种方法的时间复杂度较低，因为我们只需进行一次除法运算即可判断。但仍然需要遍历数字范围内的所有数字。

反向思考 - 生成法

既然我们需要找出所有符合条件的数字，不妨反向思考，直接生成这些数字，而不是逐个判断每个数字是否符合要求。对于第一部分，我们可以通过以下步骤生成所有符合条件的数字：

对于一个特定的数字长度 $L$ ，计算 $k = L / 2$ 。
计算 $base = 10^{k} + 1$ 。
遍历所有可能的片段值 $part$ ，如果 $part \times base$ 在给定范围内，则将其加入结果集。

范围限制

要小心， $part$ 的范围有限制，必须令 $part$ 是一个 $k$ 位数，防止生成不符合要求的数字。

比如使用 $1001$ 作为 $base$ 时， $10$ 不能作为 $part$ （生成的 $10010$ 不符合要求）；类似的， $1234$ 也不可用。

我们需要限制 $part$ 的范围为 $part \in [10^{k-1}, 10^{k})$ ，正好填充 $k$ 位数。

更进一步，由于题目最终需要的是所有符合条件的数字之和，我们可以直接使用高斯求和公式来计算这些数字的和，而不必显式地生成每个数字。算法因此变为：

对于给定的数字范围 $[low, high]$ 和每个可能的数字长度 $L$ （偶数），计算 $k = L / 2$ 、 $base = 10^{k} + 1$ 、 $left = 10^{k-1}$ 和 $right = 10^{k} - 1$ 。
计算 $part$ 的起始值和结束值，分别为 $start = \max\left(\left\lceil \frac{low}{base} \right\rceil, left\right)$ 和 $end = \min\left(\left\lfloor \frac{high}{base} \right\rfloor, right\right)$ 。
使用高斯求和公式计算 $part$ 的和，并乘以 $base$ 得到最终结果。

这样一来，时间复杂度就大幅下降了，我们不再需要遍历每个数字，而是直接计算出结果。因此结果复杂度从近似 $O(N)$ 降低到了 $O(\log N)$ （与数字位数 $\log_{10} N$ 接近线形关系）。

推广到任意数量的重复片段

有了第一部分的基础，我们可以尝试推广到第二部分，寻找由任意数量（不少于两个）相同片段组成的数字。比如数字 121212，我们可以表示为：

\begin{aligned} 121212 = & 12 \times 10^4 + 12 \times 10^2 + 12 \\ = & 12 \times (10^4 + 10^2 + 10^0) \end{aligned}

我们不难发现，这实际上只需要将原先固定的 $base$ 进行修改即可。对于由 $r$ 个相同的、长为 $k$ 片段组成的数字，我们可以将 $base$ 定义为：

\begin{aligned} base = & \sum_{i=0}^{r-1} 10^{i \cdot k} \\ = & \frac{10^{r \cdot k} - 1}{10^{k} - 1} \\ = & \frac{10^{L} - 1}{10^{k} - 1} \end{aligned}

我们可以将符合条件的数字表示为：

n = part \times \frac{10^{L} - 1}{10^{k} - 1}

基于此，我们可以设计如下算法：

对于给定的数字范围 $[low, high]$ 和每个可能的数字长度 $L$ ，计算 $k$ 的所有可能值（ $k$ 必须是 $L$ 的因数且 $k < L$ ）。
对于每个 $k$ ，计算 $r = L / k$ 和 $base = \frac{10^{L} - 1}{10^{k} - 1}$ 。
计算 $part$ 的起始值和结束值，分别为 $start = \max\left(\left\lceil \frac{low}{base} \right\rceil, left\right)$ 和 $end = \min\left(\left\lfloor \frac{high}{base} \right\rfloor, right\right)$ 。
使用高斯求和公式计算 $part$ 的和，并乘以 $base$ 得到最终结果。

但这对吗？我们来想一想。比如对于一个数字 $666666$ ，我们看看会发生什么：

\begin{aligned} k = 1 & \Rightarrow part = 6, r = 6 \\ k = 2 & \Rightarrow part = 66, r = 3 \\ k = 3 & \Rightarrow part = 666, r = 2 \end{aligned}

类似的，来看数字 $12121212$ ：

\begin{aligned} k = 2 & \Rightarrow part = 12, r = 4 \\ k = 4 & \Rightarrow part = 1212, r = 2 \end{aligned}

糟糕，这样的话，我们会多次计算同一个数字，导致结果错误。为了解决这个问题，我们需要确保每个数字只被计算一次。

那么我们到底重复计算了哪些数字？正是那些由更短片段组成的数字。比如 $666666$ 可以看作是由片段长度为 $1$ 的数字组成的，因此当我们计算片段长度为 $2$ 和 $3$ 时，就重复计算了这个数字；类似地， $12121212$ 也在片段长度为 $2$ 和 $4$ 时被重复计算。

对此我们不难发现，如果一个数字的两种分法 $k_1$ 和 $k_2$ 满足 $k_1$ 是 $k_2$ 的因数，那么较长的分法就会重复计算较短的分法所生成的数字。即：对于一个给定的总位数 $L$ ，其因数 $k$ 对应的分法，会包含所有那些由 $k$ 的因数（记为 $d$ ）所对应的分法生成的数字（其中 $d$ 也是 $L$ 的因数）。这也引出了一个核心的去重思路：对每个 $L$ ，只考虑那些“重复次数 $r$ 为质数”的分法，然后将所有结果相加。因为任何合数 $r$ 的重复模式，都可以拆分为更小的质数次重复，从而被包含在质数 $r$ 的计数中。在算法上，我们可以拆解为两步：

找出 $L$ 的所有质因数，记为 $r_1, r_2, \ldots, r_m$ ，分别计算以 $r_i$ 作为重复次数对应的结果。
使用容斥原理，去除重复计算的部分。由于质数之间互质，唯一的可能重叠计算部分即为长度为 $1$ 的片段，因此我们只需从总和中减去长度为 $1$ 的部分即可。

如此一来，我们不仅确保了结果的正确性，还保持了较高的计算效率。

核心算法实现

1
type Range = (u64, u64);
2

3
struct Puzzle {
4
    ranges: Vec<Range>,
5
}
6

7
impl Puzzle {
8

9
  fn prime_factors(mut n: u32) -> Vec<u32> {
10
      let mut factors = BTreeSet::new();
11
      while n.is_multiple_of(2) {
12
          factors.insert(2);
13
          n /= 2;
14
      }
15
      let mut divisor = 3;
16
      while divisor * divisor <= n {
17
          while n.is_multiple_of(divisor) {
18
              factors.insert(divisor);
19
              n /= divisor;
20
          }
21
          divisor += 2;
22
      }
23
      if n > 1 {
24
          factors.insert(n);
25
      }
26

27
      factors.into_iter().collect()
28
  }
29

30
  fn get_sum_invalid_ids(range: Range, n: u32, repeat: u32) -> u64 {
31
      // The pattern repeats every k = n / repeat digits
32
      let k = n / repeat;
33
      // Calculate the lower and upper bounds for n-digit numbers with the given
34
      // pattern
35
      let upper = 10u64.pow(n) - 1;
36
      let base = upper / (10u64.pow(k) - 1);
37
      let lower = 10u64.pow(k - 1) * base;
38
      // Get the overlap between the given range and (lower, upper)
39
      let (start, end) = range;
40
      let start = start.max(lower);
41
      let end = end.min(upper);
42
      // Convert back to the base range
43
      let start = start.div_ceil(base);
44
      let end = end / base;
45
      if start > end {
46
          return 0;
47
      }
48

49
      (end - start + 1) * (start + end) / 2 * base
50
  }
51
}
52

53
impl Solution for Puzzle {
54
    fn part1(&self) -> String {
55
        self.ranges
56
            .par_iter()
57
            .map(|&(start, end)| {
58
                let min_n = start.ilog10() + 1;
59
                let max_n = end.ilog10() + 1;
60

61
                (min_n..=max_n)
62
                    .filter(|n| n % 2 == 0)
63
                    .map(|n| Self::get_sum_invalid_ids((start, end), n, 2))
64
                    .sum::<u64>()
65
            })
66
            .sum::<u64>()
67
            .to_string()
68
    }
69

70
    fn part2(&self) -> String {
71
        self.ranges
72
            .par_iter()
73
            .map(|&(start, end)| {
74
                let min_n = start.ilog10() + 1;
75
                let max_n = end.ilog10() + 1;
76

77
                (min_n..=max_n)
78
                    .filter(|&n| n > 1)
79
                    .map(|n| {
80
                        // Sum of all repeating digits (e.g., 1111, 2222, ..., 9999 for n=4)
81
                        let all_same = Self::get_sum_invalid_ids((start, end), n, n);
82
                        // Get all patterns with smaller, prime repeat factors
83
                        Self::prime_factors(n).into_iter().filter(|&k| k < n).fold(
84
                            all_same,
85
                            |mut sum, k| {
86
                                sum += Self::get_sum_invalid_ids((start, end), n, k);
87
                                sum -= all_same;
88
                                sum
89
                            },
90
                        )
91
                    })
92
                    .sum::<u64>()
93
            })
94
            .sum::<u64>()
95
            .to_string()
96
    }
97
}

总结

完整代码见此处。

通过对题目的深入分析与数学方法的应用，我们成功地将问题从一个需要遍历大量数字的任务，转化为一个高效的计算问题。利用数字的结构特性和容斥原理，我们不仅提高了算法的效率，还避免了复杂的判断逻辑。虽然题目本身并不复杂，但是优化过程却是十分有趣。