题解：CF2200H Six Seven

· · 题解

警告：这个做法笔者并没有写代码验证正确性。

题意：求最小的 k 使得 v_6(a_i+k)>v_7(a_i+k)。

首先一个显然的必要性是，数字之间两两的差都得是 6 的倍数。因此，我们先给每个数加一个 m，满足 0\le m <6 并且 6|a_1+m，然后我们对每一个新的 a_i 都除掉 6 记作 a_i'。

首先假设我们在做一个判定性问题，即，给定 k，问是否满足题意。以下记 b_i=a_i'+k。这样我们就只要求 v_6(b_i)\ge v_7(b_i) 即可。

既然我们又要考虑模 6 又要考虑模 7，那么我们可以综合一下，考虑模 42。

考虑一个数对 42 取余数得结果，我们分为三类：

这样我们就解决了判定性问题。

然后我们考虑如果对于每一个 k 去做一遍判定性算法，太慢了。但是我们注意到如果 42^m|k_1-k_2，在处理 k_1,k_2 得时候，有很多重复得步骤。我们考虑合并它们。由此就可以得到以下的做法：

考虑用 42 进制表示 k（一个最小化问题却从低往高填，有点出人意料喵）。从低到高枚举每一位该填什么。假设现在考虑到填 x 并且考虑每一个 b_i+x 对 42 取余数的结果。如果全都不为 0，那么已经判断好。否则，对于那些为 0 的，我们考虑继续把 b_i+x 除掉 42 后继续枚举高位，其过程还是完全一样的。

记 V 为值域，时间复杂度 \mathcal{O}(n\log V)，空间复杂度为 \mathcal O(n+\log V)。这个时空复杂度的证明见下。

考虑每一个 b_i 建可以对应一个字符串 st_i，为 42 进制下 b_i 的表示再倒序（比如 49 = 1\times 42+ 7，那么它对应的字符串为 \tt 71）。

我们对所有 st_i 建立一棵 \rm Trie 字典树。观察到我们的算法几乎只需要访问每个结点一次。（这里的几乎是因为有进位问题，可能会多访问不超过 \mathcal O(n) 个结点）。

这个字典树的大小显然 \le n(\log_{42} V+5)。