核心思路

关键观察

1. 冲突本质：当两个数 $x$ 和 $y$ 满足 $x \equiv y \pmod{n}$ 时，它们会被分配到同一个桶中，从而产生冲突。

2. 探测原理：通过精心构造的查询序列，我们可以检测两个数是否同余模 $n$，从而逐步确定 $n$ 的值。

核心公式与构造方法

基础探测公式

对于任意整数 $a, b$，如果：

$$a \equiv b \pmod{n}$$

那么插入序列 $[a, b]$ 会产生 $1$ 次冲突（因为第二个数插入时桶中已有一个元素），否则冲突次数为 $0$。

倍数构造法

构造两个特殊序列：

• 序列 $S$：$S = \{1 \cdot L, 2 \cdot L, 3 \cdot L, \dots, k \cdot L\}$
• 序列 $T$：$T = \{(118 \cdot 1 + 1)L, (118 \cdot 2 + 1)L, \dots, (118 \cdot m + 1)L\}$

其中 $L = 9128 \times 3 = 27384$ 是一个精心选择的基数。

关键判定

计算 $collisions(S \cup T)$：

• 如果结果为 $0$，说明所有 $S$ 中的元素与 $T$ 中的元素都不同余模 $n$，进入情况一
• 如果结果不为 $0$，说明存在同余对，进入情况二

情况一：无直接冲突

采用分治搜索策略：

1. 将序列 $S$ 和 $T$ 不断二分
2. 通过合并查询确定哪半个序列包含同余对
3. 最终找到一对具体的 $(s, t)$ 满足 $s \equiv t \pmod{n}$

此时 $n$ 整除 $|s - t|$，我们得到 $n$ 的一个倍数 $x = |s - t|$。

情况二：存在直接冲突

直接寻找满足条件的 $i$，使得：

$$collisions(\{1, 1 + i \cdot L\}) = 1$$

这等价于：

$$1 \equiv 1 + i \cdot L \pmod{n} \Rightarrow i \cdot L \equiv 0 \pmod{n} $$

因此 $n$ 整除 $i \cdot L$，得到 $n$ 的一个倍数 $x = i \cdot L$。

因子消去法

在两种情况下，我们都先获得 $n$ 的一个倍数 $x$，然后通过质因数分解和验证来消去多余的因子：

对于 $x$ 的每个质因子 $p$，重复检查：

$$collisions(\{1, \frac{x}{p} + 1\}) \neq 0$$

如果检查通过，说明 $n$ 不能被 $p$ 整除，将 $x$ 除以 $p$。最终剩下的 $x$ 就是正确的 $n$。

算法优势

1. 高效性：通过分治策略将问题规模对数级减少
2. 可靠性：基于数论原理，确保正确性
3. 经济性：总花费远低于 $1,000,000$ 的限制