小欧的等差数列

OPPO 笔试真题 · 2024 秋招 · 后端岗

判题请到牛客原题提交。

题目描述

小欧有一个长度为 $n$，首项为 $a$，公差为 $d$ 的等差数列。即 $a, a + d, a + 2d, \cdots, a + (n - 1)d$。现在，小欧把这 $n$ 个数看作一个集合，每次操作可以从集合中任意选两个数 $a_i, a_j$，如果 $a_i + a_j$ 是偶数，那么可以将 $(a_i + a_j) / 2$ 加入到集合中。小欧想知道，经过若干次操作后，集合中最多能有多少个数。

输入格式

一行三个整数 $n, a, d$，表示等差数列的长度，首项和公差。

$1 \leq n \leq 10^5$

$1 \leq a, d \leq 10^9$

输出格式

输出一个整数，表示集合中最多能有多少个数。

示例

示例 1

输入：

5 1 2

输出：

9

说明：

一开始集合为 $[1, 3, 5, 7, 9]$，选择相邻两项，可以得到 $[1, 2, 3, 4, 5, 6, 7, 8, 9]$。

---

解题思路

第一步：理解问题本质

一次操作能进行，当且仅当 $a_i + a_j$ 是偶数，也就是 $a_i$ 与 $a_j$ 同奇偶；
新加入的数就是它们的平均数，落在两者正中间。

所以问题的关键是：初始集合里的数奇偶是怎么分布的，以及平均数能把「格子」插得多密。

第二步：直接模拟为什么不行

集合一旦变密，元素个数可以达到 $10^{14}$ 量级（答案本身就可能是这个规模），
两两枚举平均数完全不可行。必须找出「集合最终会长成什么样」的规律。

第三步：d 为奇数时，一个新数也造不出来

此时相邻两项相差奇数，奇偶性交替出现。两个同奇偶的数，它们的下标之差必为偶数，
设下标为 $i$ 和 $j$，则

$$\frac{(a+id)+(a+jd)}{2} = a + \frac{i+j}{2}\cdot d$$

$\frac{i+j}{2}$ 是整数，说明这个平均数本来就是集合里的一项（下标为 $\frac{i+j}{2}$）。

例如 $a=1, d=3, n=4$：集合 $\{1,4,7,10\}$，同奇偶的配对只有 $(1,7)\to 4$、$(4,10)\to 7$，
全都是已有元素。所以 d 为奇数时答案是 n。

第四步：d 为偶数时，公差可以不断减半

此时所有项与 $a$ 同奇偶，任意两项都能取平均。特别地，相邻两项
$a+id$ 与 $a+(i+1)d$ 的平均数是

$$a + id + \frac{d}{2}$$

它把集合从「步长 $d$」加密成「步长 $\frac{d}{2}$」：原来的项加上这些中点，
正好是 $a,\,a+\frac{d}{2},\,a+d,\,\dots,\,a+(n-1)d$ 这个步长为 $\frac{d}{2}$ 的等差数列。

只要步长还是偶数，就继续减半。设

$$d = 2^t \cdot m,\quad m \text{ 为奇数}$$

减半 $t$ 次后，集合变成从 $a$ 到 $a+(n-1)d$、步长为 $m$ 的完整等差数列。
而步长为奇数时按第三步的结论再操作也不会产生新数，于是最终元素个数为

$$\frac{(n-1)\cdot d}{m} + 1$$

例如 $d=2$ 时 $m=1$，集合被填成一段连续整数；$d=6$ 时 $m=3$，集合是「每隔 3 取一个」。

---

完整代码实现

import sys


def solve() -> None:
    """d 为奇数时无新数；d 为偶数时不断把公差减半"""
    data = sys.stdin.read().split()
    if not data:
        return
    n = int(data[0])
    a = int(data[1])
    d = int(data[2])

    if d % 2 == 1:
        # 同奇偶的两项下标差为偶数，中点恰好是已有的项
        sys.stdout.write(str(n) + "\n")
        return

    # 去掉 d 里所有的因子 2，得到奇数步长 m
    m = d
    while m % 2 == 0:
        m //= 2

    # 最终集合是 a, a+m, ..., a+(n-1)d 的完整等差数列
    total = (n - 1) * d // m + 1
    sys.stdout.write(str(total) + "\n")


if __name__ == "__main__":
    solve()

---

示例推演

示例 1：n = 5, a = 1, d = 2

$d = 2 = 2^1 \times 1$，所以 $t = 1$，奇数部分 $m = 1$。

轮次	步长	集合	元素个数
初始	2	$\{1,3,5,7,9\}$	5
取相邻中点 $1,3\to2$、$3,5\to4$、$5,7\to6$、$7,9\to8$	1	$\{1,2,3,4,5,6,7,8,9\}$	9

步长已是奇数 1，再操作只能得到集合里已有的数，最终 9 个：

$$\frac{(5-1)\times 2}{1} + 1 = 9$$

补充例子：n = 3, a = 1, d = 6

$6 = 2 \times 3$，奇数部分 $m = 3$。

轮次	步长	集合
初始	6	$\{1,7,13\}$
取中点 $1,7\to4$、$7,13\to10$、$1,13\to7$	3	$\{1,4,7,10,13\}$
继续取中点	3	还是这 5 个

答案是 $\frac{2\times 6}{3}+1 = 5$，与模拟一致（此时再取平均只会得到 1、4、7、10、13 中的数）。

补充例子：n = 4, a = 1, d = 3

$d$ 是奇数，直接输出初始个数 4。验证：$\{1,4,7,10\}$ 里同奇偶的数配对后，
中点分别是 4 和 7，都已在集合中。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
集合模拟两两取平均	取决于最终集合大小，可达 O((nd)²)	O(nd)	答案本身可达 1e14，不可行
判断奇偶 + 公式	O(log d)	O(1)	推荐，只做一次除 2 循环

---

易错点总结

1. 只把公差减半一次

$d = 4$ 时减半后步长还是偶数，要继续减半到奇数 1 才停；
用 while d % 2 == 0 循环才是对的。

2. 项数公式少算或多算一个

最终集合是「$a$ 到 $a+(n-1)d$、步长 $m$」的完整等差数列，项数是
$\frac{(n-1)d}{m} + 1$，间隔数加一。写成 $n \cdot 2^t$ 会差一。
比如 $n=5, d=2$：正确答案是 9，$5\times 2 = 10$ 是错的。

3. 以为 d 为奇数时也能插入新数

$d=3$ 的集合 $\{1,4,7\}$：$1$ 和 $4$ 加起来是奇数，不能操作；$1$ 和 $7$ 的中点是 $4$，已经有了。
所以答案就是 3。

4. 用首项 a 去推奇偶

$d$ 为偶数时，所有项与 $a$ 同奇偶，任意两项都能取平均，与 $a$ 具体是奇数还是偶数无关。
所以 $a$ 根本不影响答案，代码里输入了但没用。

5. 数据范围

答案可达 $\frac{10^5 \times 10^9}{1} \approx 10^{14}$，超出 32 位整数范围。
Python 整数没有这个问题，用 C++ 时要用 long long。

---

扩展思考

• 如果允许对任意两数取平均后向下取整（不再要求同奇偶）：那么相邻两项的中点就能一路填满区间，
  答案退化成 $(n-1)d+1$，与 $d$ 的奇偶无关 —— 奇偶限制正是本题的难点所在。
• 如果初始集合不是等差数列：「同奇偶取平均」的闭包仍然是可分析的，
  它会把集合按奇偶分成两类，各自在数轴上「填成格点」，格子大小与技术细节有关。
• 如果把操作换成「取两数之差」：就变成了 gcd 问题，最终集合的元素都是某个 gcd 的倍数。
• 本题的结论也可以这样记：先把公差的 2 的因子除干净，剩下的奇数部分就是最终的「格子宽度」。

---

相关题目

• 小欧找数