解题思路 | 6小时极速闯关，脑洞一定要大开开开开开
原创解题思路 | 6小时极速闯关，脑洞一定要大开开开开开
原创
各位乘风破浪的coder们，你们千呼万唤的解题思路来啦！
（原赛题直达车：一道即将尘封十几年的封印，不来尝试解开吗？） 本次解题报告由微信算法大神yueqi提供。在腾讯内部赛道中，来自微信的yueqi同学在赛题发布6小时后即破解封印、完成闯关，成为内部赛首届冠军。解题思路千万条，脑洞大开第一条，也欢迎小伙伴们在文末留言分享自己的解题报告链接！
problem 1
1+1=?
幼儿园加法。
problem 2
(x*18-27)/3-(x+7496)=0, x=
一元一次方程，小学数学。
problem 3
41*x-31*x^2+74252906=0,(x^2表示x的2次方,下同),x的某个根=
一元二次方程，初中数学。
系数看起来不太好对付，直接掏出了 wolfram。
problem 4
(1234567^12345678901234567890)%999999997=
快速幂，基本算法，大学算法或数据结构课程会讲授的内容。
problem 5
1_2_3_4_5_6_7_8_9=-497,每处_填入1个运算符+-*/,且4个运算符必须都用上,使得等式成立(答案保证唯一),表达式为? 枚举每个位置的运算符，只有 4^8=65536 种可能。涉及到表达式计算，python 等带有 eval 的语言解决起来更容易一些。但运算符只有两种优先级和一种结合性，用 C++ 等实现也不麻烦。编程入门题。
problem 6
x^5-2*x^4+3*x^3-4*x^2-5*x-6=0, x(精确到小数点后14位)=
再次掏出了 wolfram。
实际上也可以用二分法、牛顿迭代法等求解。牛顿迭代法从 0 出发只需要 20 轮就能得到所需精度。数值分析入门题。
problem 7
请输入8位数字PIN码:
完整题面：
def Hash(context):
result = md5(bytes(context, 'utf8'))
for i in range(0, 10000000):
result = md5(result.digest())
return result.hexdigest()
key=input('请输入8位数字PIN码:')
print("验证中……")
if Hash(key) == '5f4654140971c47658de19d62ba472b6':
exec(Decrypt(key, 'xxxx...xxxx'))
else:
print("PIN码错误")从这一题开始需要修改代码获取完整题面。Hash 函数的迷惑性很强，实际上可以跳过 MD5 部分，直接用 Decrypt 函数作为验证手段来破解密码。简单改造代码之后多进程暴力枚举 8 位数字，需要花点时间，但还可以接受。
有种 CTF 的感觉，算是 CTF 入入入入入门题？
problem 8
计算第8关密钥中,时间可能非常长...
完整题面：
print('计算第8关密钥中,时间可能非常长...')
stack = []
ins_len = [1] * 5 + [2] * 9 + [9, 1]
reg = [0] * 16
code = base64.b64decode('zyLpMs8CL9Oy/3QDdRlURZRGFHQHdRhURZFGIL/lv+MiNi+70AXRBtMD1wfYCNkJ5v3/iV14RWMB0n+/xgk=')
while True:
ins, r0 = code[reg[15]] >> 4, code[reg[15]] & 15
length = ins_len[ins]
if length > 1:
arg = code[reg[15] + 1 : reg[15] + length]
if length == 2: r1 = arg[0] >> 4; r2 = arg[0] & 15
reg[15] += length
if 0 == ins : break
elif 1 == ins : stack.append(reg[r0])
elif 2 == ins : reg[r0] = stack.pop()
elif 3 == ins :
if not reg[r0] : reg[15] += ins_len[code[reg[15]] >> 4]
elif 4 == ins : reg[r0] = 0 if reg[r0] else 1
elif 5 == ins : reg[r0] = reg[r1] + reg[r2]
elif 6 == ins : reg[r0] = reg[r1] - reg[r2]
elif 7 == ins : reg[r0] = reg[r1] * reg[r2]
elif 8 == ins : reg[r0] = reg[r1] / reg[r2]
elif 9 == ins : reg[r0] = reg[r1] % reg[r2]
elif 10 == ins : reg[r0] = 1 if reg[r1] < reg[r2] else 0
elif 11 == ins : stack.append(reg[r0]); reg[r0] += int.from_bytes(arg, byteorder='little', signed=True)
elif 12 == ins : reg[r0] += int.from_bytes(arg, byteorder='little', signed=True)
elif ins in (13, 14) : reg[r0] = int.from_bytes(arg, byteorder='little', signed=True)
key = str(reg[0])+str(reg[1])
exec(Decrypt(key, 'xxxx...xxxx'))看到上面的代码，我仿佛回到了大学的计算机组成原理课堂……代码模拟了一个简单的 CPU，对应一个 15 条有效指令的指令集。指令基本由 4 位指令编号和 4 位寄存器编号组成，部分指令还带有 1 或 8 个字节用于多寄存器操作和加载操作数。
指令集如下。还没有把汇编全部还给老师的同学很容易看出部分指令和控制结构的对应关系。11 号指令可以用于函数调用，2 号指令对 PC 寄存器使用时就是 return，3 号指令用于 if-else 的分支结构。
0. 1, return
1. 1, push r0
2. 1, r0 = pop
3. 1, jmp (0) PC += ins_len[3]
4. 1, r0 = !r0
5. 2, r0 = r1 + r2
6. 2, r0 = r1 - r2
7. 2, r0 = r1 * r2
8. 2, r0 = r1 / r2
9. 2, r0 = r1 % r2
10. 2, r0 = r1 < r2
11. 2, push r0; r0 += arg
12. 2, r0 += arg
13. 2, r0 = arg
14. 9, r0 = arg (8)
15. nop修改代码，阻止 PC 寄存器的修改，打印出 code 中每个地址对应的指令。
作者做题时太莽，只打印了指令编号和寄存器编号，以下汇编代码是后续人肉转换的产物，并非直接打印。过程中还打印了原代码的执行顺序用于验证。
0 GOTO 36
2 r9 = ???? // 未使用
3 if r2 == 0 then
6 return
8 PUSH r2; r2 -= 1
10 r4 = r0 * r3
12 r5 = r1 * r9
14 r4 += r5
16 r4 %= r6
18 PUSH r4
19 r4 = r0 * r7
21 r5 = r1 * r8
23 r4 += r5
25 r1 = r4 % r6
27 POP r0
28 CALL 3
30 CALL 3
32 POP r2
33 if r6 != 0 then
34 return
35 PUSH r11; r11 -= 48 // 未使用
36 r0 = 5
38 r1 = 6
40 r3 = 3
42 r7 = 7
44 r8 = 8
46 r9 = 9
48 r6 = 99999999999999997
57 r2 = 127
59 CALL 3也可以继续转换为高级语言
def func1(r2):
if r2 == 0: return
r2 -= 1
temp = (r0 * r3 + r1 * r9) % r6
r1 = (r0 * r7 + r1 * r8) % r6
r0 = temp
func1(r2)
func1(r2)
if r6 != 0: return发现这是个二元一阶常系数齐次线性递推！答案就是数列的第 2^n-1 项，其中 n=127。和 problem 4 类似，这可以用快速幂来解决，只是半群的元素从整数变成了二阶方阵。
简单解释：设递推式为 x[n]=a*x[n-1]+b*y[n-1], y[n]=c*x[n-1]+d*y[n-1]。我们将它写为矩阵形式：[x[n],y[n]]^T = [[a,b],[c,d]] * [x[n-1],y[n-1]]^T = [[a,b],[c,d]]^n * [x[0],y[0]]^T。
于是可以先用快速幂求出转移矩阵的 n 次幂，然后再与数列起始项对应的列向量相乘得到第 n 项。所涉及的加法和乘法都是模意义下的运算。这一方法只依赖于递推常系数和线性的性质，多元、高阶、非齐次都可以简单扩展得到。
本题作为最后一题，考察知识点选择了一门计算机专业的主干课程，辅以矩阵快速幂，难度陡增。
总结
感谢龙哥提供如此有趣的一组题目，题目本身通过加密层层嵌套的形式也很精巧。为了体现从零开始的知识内容，前 6 题设计上不免多有限制，对一名计算机相关行业从业者来说可能不够过瘾，但最后两题设计得十分精彩，绝对能令人沉浸其中。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。