哈希攻击

题目描述

字符串以某种方式映射到整数上的过程，称作「字符串哈希」。由这个字符串经过哈希得到的整数，我们称其为字符串的「哈希值」。以下是一种比较常用的字符串哈希公式：

$$ f(s) = ( \sum_{i=1}^{n} a_i \times b^{n-i} )\bmod p $$

其中，$a_i$ 是字符串第 $i$ 位对应字符所需要映射的值，$b$ 是小于 $p$ 的正整数，$p$ 是一个大质数。

当两个字符串完全相同时，它们的哈希值也必定完全相同。可是反之，当两个字符串的哈希值完全相同时，它们本身并不一定会完全相同。因为哈希函数最终对 $p$ 取模的操作，使得无穷无尽的字符串最终只能被映射到 $0 \sim p-1$ 的正整数上，而这就必定要产生多个不同字符串拥有同一哈希值的情况。这种两个不同的字符串具有相同的哈希值的情况，我们称其为「哈希冲突」

可是 Gino 并不害怕。他使用如下函数对字符串进行哈希，并且认为你无论如何也无法在短时间内产生无穷多的字符串，并从无穷多的字符串中找到哈希冲突的情况。

int strhash(char s[], int len, int b, int p)
{
    int val = 0;
    for (int i = 0; i < len; i++)
    {
        val = (1ll * val * b + s[i] - 'a' + 1) % p;
    }
    return val;
}

请你找到任意两个字符串，使它们满足以下条件：

• 仅由小写字母 a-z 组成
• 两者长度相同，且长度 $n$ 满足 $1 \le n \le 10^4$
• 两者不完全相同，却在给定 $b,p$ 的条件下有着一致的哈希值

输入

两个由空格隔开的正整数 $b,p$，含义与题意相同。

• 对于 $10 \%$ 的数据，$31\le b \lt p \le 1009$
• 对于 $30 \%$ 的数据，$31\le b \lt p \le 1000033$
• 对于 $100 \%$ 的数据，$31\le b \lt p \le 1000000007$

所有数据均保证 $p$ 是一个质数。

输出

两行，分别输出你找到的两个字符串，需要满足题目给出的条件。满足条件的字符串有很多组，你只需要输出任意一组即可。

输入样例

131 1033

输出样例（答案不唯一）

vda
ciu

样例解释

对于字符串 vdl，其哈希值为 $(22 \times 131^2 + 4 \times 131^1 + 1 \times 131^0) \bmod 1033 = 378067 \bmod 1033 = 1022$

对于字符串 ciu，其哈希值为 $(3 \times 131^2 + 9 \times 131^1 + 10 \times 131^0) \bmod 1033 = 52672 \bmod 1033 = 1022$

两个不同的字符串却有着同样的哈希值，因此这组输出是正确的。

注意你的输出不必和输出样例相同，只需满足题目条件即可。

---

$\mathcal{HASH HACKER}:$