6127 - 谁是卧底(d)
题目描述
在《谁是卧底》节目中，一共有 n 位参赛者，编号为 1~ n。
每位参赛者心里想一个正整数 a_i，导演组给出同一个密码 d（保证 d ≥ 2）。
- 好人会展示：b_i = a_i × d
- 卧底会展示：b_i = a_i + d
并且所有参赛者满足：1 ≤ a_i < d。
你只看到了最终展示出来的序列 b_1,b_2,...,b_n，已知恰好有一名卧底，且至少存在一组合法的原序列和密码与该序列一致。
注意：不保证合法的 d 唯一。你需要在所有合法方案中，找到尽可能大的 d，并输出该 d 对应的卧底编号。
保证最大合法 d 对应的卧底编号唯一。
输入
第一行输入一个整数 n。
第二行输入 n 个整数 b_1,b_2,...,b_n。
输出
输出一个整数，表示最大合法 d 对应的卧底编号（下标从 1 开始）。
样例
输入
5 12 18 10 30 24
输出
3
输入
6 14 21 35 11 28 42
输出
4
说明
样例解释
样例 1 可取 d=6。除第 3 人外，其余展示值都可写成某个 a_i × 6；第 3 人展示 10，可写成 4+6，因此第 3 人是卧底。
样例 2 可取 d=7。第 4 人展示 11=4+7，其余人展示值均为 7 的倍数，因此第 4 人是卧底。
数据范围
| 数据点编号 | 数据范围 | 特殊性质 |
|---|---|---|
| 1 | n \leq 10, b_i \leq 10^3 | 合法 d 唯一 |
| 2 | n \leq 100, b_i \leq 10^5 | 合法 d 唯一 |
| 3 | n \leq 100, b_i \leq 10^5 | |
| 4 | n \leq 1000, b_i \leq 10^6 | 合法 d 唯一 |
| 5 | n \leq 5000, b_i \leq 10^9 | 无特殊性质 |
| 6 | n \leq 2 \times 10^4, b_i \leq 10^9 | 无特殊性质 |
| 7 | n \leq 10^5, b_i \leq 10^9 | 卧底靠近中间位置 |
| 8 | n \leq 10^5, b_i \leq 10^{12} | b_i 含较多重复值 |
| 9 | n \leq 2 \times 10^5, b_i \leq 10^{12} | 无特殊性质 |
| 10 | n \leq 2 \times 10^5, b_i \leq 10^{12} | 无特殊性质 |
来源
2026年常州“信息与未来”小学生编程比赛线上
标签
