CF1184A3 Heidi Learns Hashing (Hard)

现在 Heidi 已经准备好破解 Madame Kovarian 的哈希函数了。 Madame Kovarian 对于名字的更改有一套非常严格的规则。只有当对两个名字使用如下哈希函数后发生碰撞时，这两个名字才能互换。然而，这个哈希函数是有参数的，因此总可以找到一组参数使得发生碰撞。Heidi 决定利用这一点为自己谋利。 给定两个长度相等为 $n$ 的字符串 $w_1$ 和 $w_2$，它们均由小写英文字母组成，以及一个整数 $m$。 考虑如下标准多项式哈希函数： $$ H_p(w) := \left( \sum_{i=0}^{|w|-1} w_i r^i \right) \bmod p $$ 其中 $p$ 是某个质数，$r$ 是满足 $2\leq r \leq p-2$ 的某个整数。 你的目标是找到 $r$ 和质数 $p$（$m \leq p \leq 10^9$），使得 $H_p(w_1) = H_p(w_2)$。 字符串 $w_1$ 和 $w_2$ 是从所有长度为 $n$ 的小写英文字母字符串中独立随机采样得到的。

第一行包含两个整数 $n$ 和 $m$（$10 \le n \le 10^5$，$2 \le m \le 10^5$）。 第二行和第三行分别包含字符串 $w_1$ 和 $w_2$，它们是从所有长度为 $n$ 的小写英文字母字符串中独立随机采样得到的。

输出两个整数 $p, r$。 $p$ 应为区间 $[m, 10^9]$ 内的质数，$r$ 应为满足 $r \in [2, p-2]$ 的整数。 保证至少存在一个解。如果有多个解，输出任意一个均可。

在第一个样例中，注意虽然 $p=3$ 且 $r=2$ 也会导致哈希碰撞，但这不是一个正确的解，因为 $m=5$，因此我们需要 $p\geq 5$。 在第二个样例中，我们注意到末尾多了一个 'g'。我们只是没有意识到 “River Song” 和 “Melody Pond” 的长度不同…… 由 ChatGPT 4.1 翻译