看到这样一段很短的完整 C 程序,可以输入两个个位数并算出和……长度只有 41 字节!其原理是?

代码

main(n){gets(&n);putchar(n%85+5);}

输入 1 1, 1 2 等,即可算出 1+1 和 1+2,但对一些输入不能给出正确结果,如 5+5,因为输出已经变成 2 位数了。

main(n){gets(&n);printf("%d\n",n%85-43);}

而上面这段代码可以过 POJ 1000。(Volltin 透露,这是因为 POJ 1000 的数据太弱了,只有个位数加法……)

原理

我很好奇这个原理是什么,尤其是 85、5、43 这些奇怪的数字从何而来。

就以 1 2 为例,实际上会写到 n 里 4 个字节,即 {'1', ' ', '2', 0},在小端机器上,高地址对应低位,转换为十进制整数是 3285041,十六进制是 322031,二进制是 00110010 (0x32) 00100000 (0x20) 00110001 (0x31)。

输入分别对应 n 的高 8 位和低 8 位,确实可以很容易分离开来相加,但这里取巧的是模 85。设输入分别是 $a$ 和 $b$,把这个数字拆分开,就是

$$(b+48) \times 2^{16} + 32 \times 2^8 + (a+48) \times 2^0$$

要用模 $M$ 的方法求出 $a+b$,只需找到一个 $M$,使得 $$(b+48) \times 2^{16} + 32 \times 2^8 + (a+48) \times 2^0 \equiv a+b+C \pmod M$$ 现在已经可以用穷举的方法找出来这个 $M$ 了。但我们显然不会满足于此:原理到底是什么?

因为 $$2^8 \equiv 2^{16} \equiv 1 \pmod{85}$$ 所以 $$(b+48) \times 2^{16} \equiv b+48 \pmod{85}$$ $$32 \times 2^8 \equiv 32 \pmod{85}$$ 又显然有 $$48 \leq a+48 \leq 57 \lt 85$$ 因此 $$(b+48) \times 2^{16} + 32 \times 2^8 + (a+48) \times 2^0 \equiv b+48+a+48+32 \equiv a+b+43 \pmod{85}$$

现在就导出了最终结果,得到了 43 这个数字。而 +5 则显然与 ASCII 码有关。可见,这段代码的本质是用模来算加法,这是我以前没想过的。关键就在 $2^{16} \equiv 1 \pmod{85}$。在 $[1,2^8)$ 区间内满足该性质的数字有 3, 5, 15, 17, 51, 85, 255,也就是说,不止 85 可以这么玩!

研究完了,可以去吃饭咯!😁