2728 乘法破译

#结论，#进制

0？

首先注意到，与 0 相乘，结果一定得零。
在字母上表示，就是一列数的所有位相同。

1？

然后注意到，与 1 相乘，结果一定等于自身。
由于另一个乘数 $\in [0, p-1]$，因此不会进位。
所以高位一定只有一种字母（代表 0）。

2？

继续注意到，于 2 相乘，要么不进位（高位为0），要么高位为 1。
高位有两种取值。

n？

根据 2 的经验，我们想到可以判断这一列数的高位有多少种取值。 对于大于 0 的数，如果这一列的高位取值有 $k$ 个，那么这个字母对应的数是 $k+1$。

算法流程

• 首先查找 0：所有字母都相同的一列对应的数字就是 0。
  • $\operatorname{O}(n^2)$。
• 判断大于 0 的数：如果这一列数中高位取值有 $k$ 个，那么这个数就是 $k+1$。
  • $\operatorname{O}(n^2)$。

省流：找规律 或者说 你被耍了

$0$ 显然可以一眼看出

那么对于 $x \in [1,p-1]$，ta 乘上 $y \in [1,p-1]$ 最大是 $x(p-1)$，进一位要 $p$，那么 $x(p-1)=xp-x \ge xp-p$，即最多进 $(x-1)$ 位。

所以直接统计（广义上的）十位有多少个不同的数即可。

把 $0$ 特判掉，然后注意到对于 $k\in(0,p)$ 有 $k=|\{\lfloor\frac{kx}{p}\rfloor\mid x\in[0,p)\}|$ 。