破解东京大学2013年招生海报谜题

前文已经说过了，201^^3是个天文数字，肯定不需要计算的。一般ACM里遇到了大数，那肯定是有周期性的，最后往往求mod解决。注意到前面的密匙“THEUNIVERSITYOFTOKYO”本身就是一个周期，于是hankcs用自己的魔方程序跑了下，发现了周期。

我们定义每次旋转魔方（比如执行T）为1步，让程序按照密匙一直旋转，发现20160步后魔方还原了，那么此20160就是周期。也就是说在20160步内肯定已经破解了此魔方，假设是在第n * 20步(20是密匙的长度)的时候破解了，那么剩下的201^^3 – n * 20 步都是耍花招骗人的。由于密匙有长度20，需要将周期除一下：20160 / 20 = 1008。

问题归结于求n，由周期性可知n = 201^^3 % 1008。

hankcs并不了解数论，但是还是搜索到一个有用的公式：

(a * b) % c = ((a % c) * (b % c)) % c

看到这里hankcs明白201^^3 % 1008仍然含有一个大数，大数怎么办？还是一板斧，找周期！hankcs编写了一段程序求解201^x % 1008（x = 1 …… 1024）并从中发现了周期规律：

201
81
153
513
297
225
873
81
153
513
297
225
873

从第二个余开始都在重复着周期为6的周期串。hankcs并不了解数论，所以这里只是依据“现象”推断这就是一个周期串。如果读者朋友能够证明的话，请一定赐教。今天发现这个完全可以用数学归纳法证明……

那么问题进一步简化为201²⁰¹ % 6 等于多少的问题。不过201²⁰¹仍然是个大数，怎么办？仍然靠周期一板斧！继续用前面的程序求解201^x % 6（x = 1 …… 1024）并从中发现了周期规律：

3
3
3
3
3
3
3
3
3
3

这下不用我说明了，201^x % 6 = 3是板上钉钉的事情了。

于是201^^3 % 1008 = 第一个列表中第 (201^x % 6 – 1) % 6 + 1 = 2 个数（先减一后加一是因为周期从第二个数开始），也就是153，n = 153 ！没有严密的证明，浪人的剑法只要夺命就好了。

于是重复153次密匙，也就是旋转153 * 20 = 3060 步就能破解魔方，将3060代入魔方程序解出最终结果：

Cong
ratu
lati
ons!
Follow the link.
http://www.is.s.
u-tokyo.ac.jp/is
t_ueno_yuuka
Grad
Sch
of
IST

看来谜题的答案就是让我Follow the link. http://www.is.s.u-tokyo.ac.jp/ist_ueno_yuuka ，于是hankcs复制此url到地址栏回车，结果看到：

这句话的意思是，已结束这个页面的公开展示。想想也不奇怪，海报是5月份贴出来的，现在都11月份了。反正我破解了这个谜题，这就是我要的结果。

昨天晚上开始熬夜到2点，上午精读课上终于解明此题的时候，hankcs简直要无视讲台上的石津先生狂笑起来。也许这个简陋的画面对hankcs来说，胜于一切红颜：

 知识共享署名-非商业性使用-相同方式共享：码农场 » 破解东京大学2013年招生海报谜题