企业官网建设流程全解析

Hash Killer 系列做到第四代，已经不是单纯找两个碰撞字符串那么简单了。我拿到题的第一反应是：给你一个目标哈希值H_target，要求构造一个指定长度的字符串，让这个最常见的h = h * P + c哈希函数算出来正好等于它。更麻烦的是，每个字符必须落在给定的字符集里，不能随便填。

第一直觉是倒推最后一位字符——反正前面 n-1 位随便填，最后一位解同余方程就行。但一试就知道不行：解出来的候选值往往在合法字符集之外，而且这个“往往”几乎等于“必然”。卡了一阵之后才意识到，这道题真正要用的不是暴力枚举，而是两件数论工具：欧拉定理和逆元。这篇博文就把这套构造思路完整拆开，从哈希的展开式讲到最终的构造代码，适合被这题卡住、或者想彻底搞懂哈希线性结构的人。

1. 一个看似无解的反向哈希题

1.1 题目到底在问什么

先把问题定义清楚。假设哈希函数是：

hash = 0 for ch in s: hash = (hash * P + ch) mod MOD

其中P是基数，MOD是模数，字符串由某个字符集C组成，长度固定为n。现在给出一个目标值H_target，要求你构造出满足hash(s) == H_target的字符串。

这个定义几乎就是 Hash Killer IV 的抽象核心。前几代 Hash Killer 是让你“找两个串碰撞”，这代反过来，给定了哈希值本身，让你逆构造。看起来像是解方程，但字符串的离散字符集让问题一下子变成了组合搜索。

这种“反向构造”在实际竞赛中出现得不多，但一旦出现就会卡住一大批人。原因很简单：我们习惯正向计算哈希，很少有人反过来思考“这个值的每一个位是怎么叠加出来的”。所以第一步不是写代码，而是把哈希函数彻底展开。

1.2 第一直觉为何失败

很多人第一反应是从后往前解。设前 n-1 位算出的中间值是h_{n-1}，最后一位字符是x，那最后一步需要满足：

h_{n-1} * P + x ≡ H_target (mod MOD)

所以：

x ≡ H_target - h_{n-1} * P (mod MOD)

这个式子看起来毫无问题，问题在于x必须属于字符集C。在模MOD下，x是一个确定的同余类，而不是一个区间。如果MOD很大而|C|很小，那么随机填前面 n-1 位，解出的x落在C里的概率大约是|C| / MOD。

举个小例子，MOD = 101，字符集只有 10 个数字，那每次命中概率只有 10% 左右。如果把模数换成10^9 + 7，字符集 26 个字母，命中概率就低到约2.6e-8。枚举前面串直到命中，期望尝试次数要上亿次，显然不现实。

所以这题的关键不是“撞”，而是“设计”。

2. 展开哈希公式：每个字符都是一次带权投票

2.1 从递推式到加权和

把递推式完全展开，你会得到一个非常漂亮的线性表达式：

hash(s) = c_1 * P^(n-1) + c_2 * P^(n-2) + ... + c_(n-1) * P + c_n (mod MOD)

也就是说，整个哈希值是每个字符乘以对应的P的幂再求和。这和十进制数本质上没有区别：P = 10的时候，字符串就是一个十进制数，每个位置的权重是10的幂。只不过哈希模掉了MOD，并且字符可以大于等于P。

这个展开式有下面三个直接推论：

第一，从右往左看，第i个字符的权重是P^(n-i)，越靠前的字符权重越高。这意味着改动前面的字符，对哈希值的影响通常比改动后面的字符大得多。

第二，整个哈希是每个字符贡献的线性叠加，没有任何交叉项。字符之间不互相影响，这是所有后续操作的基础。

第三，如果把某个位置的字符从c改成c + Δ，那么哈希值的变化量固定为Δ * P^(权重指数)，与其他位置的字符完全无关。

最后一条其实才是真正的突破口。它告诉我们：修正哈希值不一定要重新构造整个串，可以先随便填一个“种子串”，再去某个指定位置做一次定点修改，把差值补上。

2.2 线性修正是唯一的突破口

假设我们已经有了一个种子字符串seed，它的当前哈希值是h0，和目标值相差：

delta = (H_target - h0) mod MOD

现在想通过在某个位置修改字符来消除这个delta。如果修改的是距离末尾w个字符的位置（也就是它的权重是P^w），字符变化量Δchar需要满足：

Δchar * P^w ≡ delta (mod MOD)

这又是一个同余方程。它在什么情况下一定有解？如果P^w在模MOD下可逆，那解就是唯一的：

Δchar = delta * (P^w)^(-1) (mod MOD)

这里的(P^w)^(-1)就是逆元。你看，逆元就这么自然地出现了，不是我们硬要用它，而是线性方程两边同时消去一个因子时，除法在模世界里只能通过乘逆元来完成。

3. 逆元登场：把“哈希差”兑换成“字符增量”

3.1 同余方程里的除法

模意义下的除法和整数除法完全不同。要计算a / b (mod MOD)，不能直接做除法，必须先求出b的逆元b^(-1)，然后计算a * b^(-1)。

这里也是一样：我们想从delta反推出Δchar，但Δchar前面乘了一个P^w。要把它“除”掉，就必须乘上P^w的逆元。

那么P^w什么时候有逆元？答案是gcd(P^w, MOD) = 1，也就是gcd(P, MOD) = 1。这就是为什么哈希设计里P和MOD必须互质——如果它们不互质，这个反向构造问题从一开始就无解。

实际竞赛题目通常都会保证这一点。比如MOD是大质数、P取一个小质数，或者MOD = 2^64、P取任意奇数，都能保证互质。

3.2 三种求逆方式怎么选

求逆元有几种常见方法，它们的适用条件不太一样：

费马小定理是最常用的，因为竞赛里模数经常是质数。但如果哈希的模数是2^64这种自然溢出，费马小定理就失效了，只能用欧拉定理扩展版，或者直接扩展欧几里得。

我在实际写题时习惯首选扩展欧几里得，因为它不要求模数是质数，逻辑上也最直白。欧拉定理求逆的好处在于和题目名字直接呼应，而且只需要先算一次φ(MOD)，后续所有逆元都可以用快速幂批量算。

3.3 单点补丁远远不够

现在有了逆元，看起来单点修正已经能解决问题了：随便选一个位置，算出Δchar，如果新字符还在字符集里就大功告成。

问题在于，“如果”这个条件太苛刻。Δchar是一个模MOD下的确定值，可能是一个很大的数，也可能落在字符集外面。比如字符集是'a'到'z'，而Δchar解出来是 200，那就完全没法用。每个位置只有一个“唯一解”，没有调整余地，所以单点补丁的成功率依然很低。

到这一步，我们需要更大的自由度。不是改一个位置，而是“追加”一段独立的字符块，用一整段字符来精确调节哈希值。这就轮到欧拉定理登场了。

4. 欧拉定理解锁的“调整块”技巧

4.1 追加一个字符块会发生什么

假设已经有一个种子串，计算到当前哈希值h0。现在不让它结束，而是继续往末尾追加t个完全相同的字符x。

每追加一个x，哈希都会前进一次。追加完t个之后，新的哈希值是：

h_out = h0 * P^t + x * (P^(t-1) + P^(t-2) + ... + P + 1) (mod MOD)

记：

V(t) = P^(t-1) + P^(t-2) + ... + P + 1

那么：

h_out = h0 * P^t + x * V(t) (mod MOD)

这里有两个未知量：t和x。如果我们能控制t，让P^t变成某个方便的常数，同时让V(t)可逆，那就又能解出x了。这就是欧拉定理的用武之地。

4.2 为什么偏偏选 d-1 个字符

欧拉定理说：如果gcd(a, MOD) = 1，那么a^φ(MOD) ≡ 1 (mod MOD)。但这个上界往往不是最小的，真正有用的最小正周期叫“阶”，记作d，满足P^d ≡ 1的最小正整数。而且d一定是φ(MOD)的因数。

我们最想用的一个性质是：当t恰好等于d时，P^t ≡ 1，这时：

h_out = h0 * 1 + x * V(d) = h0 + x * V(d) (mod MOD)

如果V(d)在模MOD下等于 0，那么追加d个任意字符后哈希值完全不变。这正是构造碰撞字符串的常见手段。

但我们的目标是调节哈希到任意目标，哈希完全不变就起不到调节作用了。所以要换一个角度：让t = d - 1。

因为P^d ≡ 1，所以：

P^(d-1) ≡ P^(-1) (mod MOD)

也就是说，P^(d-1)就是P的逆元。这一步就非常舒服了，因为P^(-1)是可以通过逆元直接算出来的常数。

与此同时：

V(d-1) = P^(d-2) + ... + P + 1

在P^d ≡ 1的背景下，V(d-1)也有一个巧妙的封闭形式：

V(d-1) = (P^(d-1) - 1) / (P - 1) (mod MOD)

只要P-1可逆，这个公式就可以直接算。就算P-1不可逆，也可以递推预处理V，这个坑后面专门说。

于是，追加d-1个相同字符x后的哈希值变成：

h_out = h0 * P^(-1) + x * V(d-1) (mod MOD)

这个式子只有一个未知数x，所以：

x = (H_target - h0 * P^(-1)) * V(d-1)^(-1) (mod MOD)

只要x落在合法字符集C里，整个构造就完成了。

4.3 多个调整块：把一个方程扩成一组方程

单块的问题依然存在：解出的x可能不在字符集里。这时候可以用两个调整块来增加自由度。

所谓两个调整块，就是先追加d-1个x，再追加d-1个y。整体的变化是：

h_out = [h0 * P^(d-1) + x * V(d-1)] * P^(d-1) + y * V(d-1) (mod MOD)

整理一下：

h_out = h0 * P^(2d-2) + V(d-1) * ( x * P^(d-1) + y ) (mod MOD)

因为P^(d-1) ≡ P^(-1)，所以P^(2d-2) ≡ P^(-2)。整个表达式依然保持线性。此时x和y两个字符都可以选择，方程只有一个约束，所以先随机定x，再解y；如果解出的y也不在字符集里，就换x，或者换种子串重试。

推广到k个调整块，整体表达式就是一个以块字符为系数的线性组合：

h_out = h0 * P^(k(d-1)) + V(d-1) * Σ ( x_j * P^((k-j)(d-1)) ) (mod MOD)

这个形式已经足够清晰。每个调整块的长度都是d-1，所以总长度由种子串长度加k*(d-1)构成。我们在构造时可以根据需要任意调整种子串长度和块数量。

5. 完整构造流程与手工验证

5.1 算法流程

综合上面的推导，一个完整的构造算法可以这样设计：

1. 输入模数MOD、基数P、目标值H_target、总长度n、字符集C。
2. 计算P在模MOD下的阶d。方法是先算出φ(MOD)，再枚举它的因子，找到最小的d满足P^d ≡ 1。
3. 确定调整块长度t = d-1，调整块数量k，种子串长度s = n - k*t。
4. 随机生成种子串，长度s，每个字符都从C里取，计算它的哈希值h0。
5. 计算目标差值：

Z = (H_target - h0 * P^(k*t)) * V(t)^(-1) (mod MOD)

6. 解 k 个块字符，满足：

x_1 * P^((k-1)*t) + x_2 * P^((k-2)*t) + ... + x_k ≡ Z (mod MOD)

7. 从高位到低位依次解，先随机选前面的块字符，最后一位用逆元解出。如果最后一位不在C里，换种子串或换前面块的字符重试。

8. 把种子串和所有块字符拼起来，得到最终字符串。

这里每一步的“随机重试”都有明确的概率意义：每换一个种子串，h0都会变化，最终解出的块字符也会变化，所以重复尝试能不断逼近合法解。理论上重试次数足够多时，成功率会趋近于 1。

5.2 C++ 参考实现

下面是一段可直接套用的核心代码，省略了随机生成细节，只保留数学骨架：

using int64 = long long; int64 mod_pow(int64 a, int64 e, int64 mod) { int64 res = 1 % mod; while (e > 0) { if (e & 1) res = res * a % mod; a = a * a % mod; e >>= 1; } return res; } int64 mod_inv(int64 a, int64 mod) { // 用扩展欧几里得求逆元，要求 gcd(a, mod) == 1 // 也可以用费马小定理，但扩展欧几里得更通用 int64 b = mod, x = 1, y = 0; while (b) { int64 q = a / b; int64 t = a % b; a = b; b = t; t = x - q * y; x = y; y = t; } // 此时 a 是 gcd，x 是逆元 if (x < 0) x += mod; return x; } // 计算阶 d：最小的 d 使得 P^d ≡ 1 (mod MOD) int64 order_of(int64 P, int64 MOD, int64 phi) { int64 d = phi; // 枚举 phi 的所有质因子，尝试约简 for (int64 i = 2; i * i <= phi; i++) { if (phi % i == 0) { while (d % i == 0 && mod_pow(P, d / i, MOD) == 1) d /= i; while (phi % i == 0) phi /= i; } } if (phi > 1 && mod_pow(P, d / phi, MOD) == 1) d /= phi; return d; }

实际构造时，重点就在那几个逆元计算上。V(t)的逆元、P^(-1)的逆元、P^(-2)的逆元，全部用mod_inv一次搞定。

5.3 手工算一遍：MOD=101, P=10, target=42

纸上谈兵没什么感觉，我拿一个小模数完整算一遍。设：

MOD = 101 P = 10 H_target = 42 字符集 C = {0, 1, 2, ..., 9}

先求阶。10^2 = 100 ≡ -1 (mod 101)，所以10^4 ≡ 1 (mod 101)，阶d = 4，d-1 = 3。

取两个调整块，每个长度为 3，种子串长度取 2，总长度为 8：

s = 种子串长度 = 2 k = 2 V(3) = 10^2 + 10 + 1 = 100 + 10 + 1 = 111 ≡ 10 (mod 101) P^3 = 1000 ≡ 91 ≡ -10 (mod 101) P^6 = 10^6 = (10^3)^2 = 91^2 = 8281 ≡ -1 (mod 101)

种子串选"59"，也就是c1=5, c2=9。种子部分的哈希值：

h0 = 5 * 10 + 9 = 59

追加第一个块x、第二个块y之后：

h_out = [h0 * P^3 + x * V(3)] * P^3 + y * V(3) = 59 * (-10) * (-10) + x * 10 * (-10) + y * 10 = 5900 - 100x + 10y (mod 101)

逐项取模：

5900 mod 101 = 5900 - 101*58 = 5900 - 5858 = 42 100 mod 101 = -1

所以：

h_out = 42 + x + 10y (mod 101)

目标是42，于是需要：

x + 10y ≡ 0 (mod 101)

在x,y ∈ {0..9}里面，直接取x = 0, y = 0就满足条件。最终字符串是：

"59000000"

验证一遍：

h = 5 h = 5*10 + 9 = 59 h = 59*10 + 0 = 590 ≡ 85 h = 85*10 + 0 = 850 ≡ 42 h = 42*10 + 0 = 420 ≡ 16 h = 16*10 + 0 = 160 ≡ 59 h = 59*10 + 0 = 590 ≡ 85 h = 85*10 + 0 = 850 ≡ 42

最后恰好得到42。整个过程可复现，手算也能算清楚。

6. 真实场景里的坑：模数是 2 的幂时怎么办

6.1 P-1 不可逆不等于没法做

竞赛里哈希经常用自然溢出，也就是MOD = 2^64。这个模数下P只要取奇数，就一定和MOD互质，所以欧拉定理和逆元的“大前提”都成立。

但有一个隐藏问题：P-1是偶数，和2^64不互质，所以等比数列求和公式里的除法就不能用了。上一节我用封闭形式计算V(t)时，默认了P-1可逆；在2^64下这个条件不成立。

解决办法是不要碰除法，直接用递推求V(t)：

V(0) = 0 V(i) = V(i-1) * P + 1

预处理到需要的长度即可。如果t很大，可以用矩阵快速幂算等比数列前缀和，避免 O(t) 遍历。

6.2 阶 d-1 是奇数时 V 一定可逆

在MOD = 2^64下，P是奇数，所以P的阶d一定是2的某个幂。此时d-1是奇数。

再看V(d-1)：

V(d-1) = P^(d-2) + P^(d-3) + ... + P + 1

这里一共有d-1项，每一项P^i都是奇数。奇数个奇数相加，结果一定是奇数。在模2^64下，奇数和所有偶数都不互质，所有奇数都和2^64互质。

所以我们得到一个非常漂亮的结论：当MOD是2的幂、P是奇数时，只要取调整块长度t = d-1，那么V(t)一定可逆。也就是说，前面构造公式里的V(t)^(-1)一定存在，直接算就行。

这个细节在真正写代码时特别关键。我在本地测试时一开始直接套等比公式，结果因为P-1没有逆元，程序直接崩了。后来改成先判断gcd(P-1, MOD)，再决定用公式还是递推，问题才解决。

6.3 随机化重试是最后的工程兜底

即使数学原理正确，构造算法也未必一次成功。原因很简单：解出来的块字符不一定落在字符集里。这时候不要死磕单次构造，而是把种子串随机化，多试几次。

每次随机生成种子串，都会得到一个不同的h0，从而解出不同的块字符。只要字符集大小和模数的比值不是小到离谱，几十次甚至几千次重试通常都能命中。我在实现时习惯设定一个最大重试次数，比如 10000 次，如果超过就直接返回无解。实际做题时，这个方案非常稳定。

如果字符集实在太小，比如只有 26 个字母，而模数是10^9+7，单块重试成功率很低，那么可以增加调整块数量，因为每多一个块就多一个可以自由选择的字符；还可以调整总长度，让种子段的长度变化，扩大随机搜索空间。

说到底，算法竞赛里的构造题不是每次都要一次成功，关键是把随机重试和数学推导结合起来，让成功率可控。

7. 写在最后的一点体会

这道题给我的最大启发是：遇到反向构造类问题，先别急着枚举，先把表达式写成“已知量 + 未知量×系数”的线性结构，再看哪些系数可以用数论工具预处理。逆元解决的是“怎么把系数消掉”，欧拉定理解决的是“怎么让系数变得可控”，两者缺一不可。

我个人的习惯是，拿到这种题先草稿纸推导半小时，推导过程中反复问自己：每个未知数真的自由吗？系数是否可逆？如果不可逆，能不能换一个长度参数让系数变得可逆？这些问题想清楚了，代码反而是最轻松的一步。

另外，如果后续要扩展，这个技巧还能用到别的“给结果反推输入”的哈希题里，核心思路都差不多：展开、求逆、找周期、凑字符。希望这篇拆解能帮到正在被 Hash Killer 系列折磨的人。