零
源码不长，先整体梳理一遍逻辑
输入长度是16字节的字符串，先经过 createKey 函数处理：每个字符根据范围加175或100（这里是多解的产生来源），然后两字节一组结合索引生成关键的中间变量 keywords1。
接下来由 keywords1 变量生成了一个 Q 变量，然后用 Q 分别除以 keywords1 的每个值，得到另一个关键的中间变量 finalkey。
cheakkey 函数对 finalkey 做检查。其中 finalkey 的第一个和最后一个值直接由 rememberkey 给出；中间的6个值则经过运算后与 remembermode 对比。
最后开始之前还需要判断一下 Python 的版本。注意到 Q 和 keywords1 都是整数，Q/keywords1[0] 得到的 rememberkey[0] 是浮点数，所以这份代码是 Python3 的。
（单斜线除法运算符 / 在 Python2 中默认是整数运算，在 Python3 中是浮点数运算）
数据变化过程是 serial -> keywords1 -> finalkey -> remember，最终结果已知，需要逆推回原始的 serial。
做题之前还是要先整体预估一下难度：serial -> keywords1 的转换看起来很容易逆推；finalkey -> remember 的转换的逆推不太直观，但逻辑清晰，代码不长，需要花一些精力分析；keywords1 -> finalkey 的转换中 Q 的计算过程非常复杂，似乎也没有逻辑，看起来很难。
虽然 Q 的计算过程看起来很劝退，但无论如何，要解出题目，serial -> keywords1 以及 finalkey -> remember* 的计算过程是必然要逆推的，所以计划是先把这两部分做出来，再集中精力搞 Q 的计算。
壹
注意到任取 i ∈ [0, 8)，keywords1[i] * finalkey[i] 都是相同的值（这个值就是 Q），即任意一对 keywords1 与对应的 finalkey 成反比。
finalkey[0] 和 finalkey[7] 分别等于已知值 rememberkey[0] 和 remember[1]，带入上面的等式即可得知 keywords1[0] 和 keywords1[7] 的比值。
这里，一个重要突破口是： keywords1 都是整数。
比值是一个已知的浮点数，而比值接近于该值的整数对就是此浮点数的分数近似。
理论上可以通过连分数展开寻找最佳分数近似，但是本题中不需要，因为 keywords1的取值范围有限 。
每个 keywords1 由原始输入的两个字符+索引位置生成，按照比赛规则，程序的合法输入字符集是ascii码范围[33,126]，因此 keywords1 的取值不超过 (126+1-33)**2 * 8 = 70688 种。这个数量级可以直接遍历打表：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | validchars = range(33,126+1)
validkeywords1 = {}
for a in validchars:
for b in validchars:
for c in range(8):
aa = a+175 if a<=57 and a>=48 else a+100
bb = b+175 if b<=57 and b>=48 else b+100
k = aa**2 * bb + c**2
if k in validkeywords1:
ttt = validkeywords1[k]
else:
ttt = []
ttt.append((chr(a),chr(b),c))
validkeywords1[k] = ttt
|
去重之后只有 64030 个不同的值。这里把原始的两个字符以及索引位置一起保存起来方便最后一步还原到原始输入。
贰
根据已知等式 keywords1[0] * rememberkey[0] == keywords1[7] * rememberkey[1]，如果同时遍历 keywords1[0] 和 keywords1[7]，需要 64030*64030 次循环，不能接受。
对上式简单变形得到：keywords1[7] == keywords1[0] * rememberkey[0] / rememberkey[1]，所以可以只遍历 keywords1[0] 然后检查计算得到的 keywords1[7] 是否为整数判断等式是否成立。
（考虑浮点误差，不能直接取等，这里先四舍五入到最近的整数再计算差值的绝对值）
1 2 3 4 5 6 | rmk1 = rememberkey[0] / 1e47
rmk2 = rememberkey[1] / 1e47
for a in validkeywords1:
b = a*rmk1 / rmk2
if abs(b-int(b+0.5)) < 0.0001:
print(a,b, abs(a*rmk1-b*rmk2))
|
这段代码得到了几个输出：
1 2 3 4 5 6 7 8 9 10 11 | 6967309 6279110.000053573 0.0
3824797 3447001.000081223 0.0
5038864 4541148.000082952 0.0
7793972 7024118.999937788 0.0
2551525 2299496.999901496 0.0
6762501 6094532.000012097 0.0
7942025 7157547.999977535 0.0
3359651 3027800.000084679 0.0
9258496 8343984.000000002 0.0
6523150 5878822.999934331 0.0
3005565 2708688.999915321 0.0
|
其中 8343984.000000002 这个数值非常引人注意，因为其他的值精确度只在小数点后4位，而它的精确度最高，达到了8位，合理猜测它就是唯一要找的值。此外经过验证，8343984 也是 validkeywords1 的合法取值。
到目前为止，可以确定 keywords1[0] == 9258496，keywords1[7] == 8343984。它们分别与 rememberkey 相乘可得到 Q 的近似值 3.54457695310952e+54 ( 3.544576953109519e+54 )
叁
从 keywords1 的其余6个值到 remembermode 的转换，中间经过了 mode1~mode4 以及 Mode1~Mode2。Mode* 值不大且是两个整数的乘积（由doom函数可知），可以先尝试分解质因数：
1 2 3 4 | Mode1 = 30413574359725275612744778689984 ->
primes1 = [2, 2, 2, 2, 2, 2, 3, 3, 3, 19, 19301, 5651461, 18765679, 452548673]
Mode2 = 49715060849837149374468109364128 ->
primes2 = [2, 2, 2, 2, 2, 13, 29, 181, 353, 641, 929, 270532579, 400359419]
|
Mode* 的值来自于 mode* ，因此有必要先对 mode* 的取值范围进行估计。
mode* 来自于 finalkey，finalkey 来自于 Q 和 keywords1。现在 Q 的近似值和 keywords1 的取值范围都已知，因此可以估计出 finalkey 的取值上下界：
1 2 3 | approximateQ = 3.54457695310952e+54
finalkeyMin = approximateQ / max(validkeywords1)
finalkeyMax = approximateQ / min(validkeywords1)
|
继而可以估计出 mode* 的取值上下界：
1 2 | modeMin = int((finalkeyMin/finalkeyMax) * 10**16)
modeMax = int((finalkeyMax/finalkeyMin) * 10**16)
|
已知 Mode* 是两个 mode* 的较小值乘以差值的绝对值，所以如果把 Mode* 分成两个整数乘积的形式，则其中一个整数必然要落在 [modeMin, modeMax] 的范围内。
肆
现在问题转换为了：已知一个整数列表（Mode的质因数分解列表），从中选择若干个数，使得选出的数的乘积位于某个范围内（[modeMin, modeMax]）。
（有种背包问题的感觉） 高端算法写不来（这种规模的数据大概也不需要高端算法），写了个简单的递归搜索：
（根据最后一个数是否包含在选择中，用不同的上下界两次递归调用此函数）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | def select(primes, bound):
if len(primes) == 1:
if bound[0] <= primes[-1] <= bound[1]:
return [[primes[-1]]]
else:
return []
c = primes[-1]
if c > bound[1]:
return []
answer = []
r = select(primes[:-1], (bound[0]//c, bound[1]//c+1))
for rr in r:
answer.append([c, *rr])
r = select(primes[:-1], (bound[0], bound[1]))
for rr in r:
answer.append(rr)
return answer
primes1 = [2, 2, 2, 2, 2, 2, 3, 3, 3, 19, 19301, 5651461, 18765679, 452548673]
primes2 = [2, 2, 2, 2, 2, 13, 29, 181, 353, 641, 929, 270532579, 400359419]
selects1 = select(primes1, (1884036290872497,53077533848188232))
selects2 = select(primes2, (1884036290872497,53077533848188232))
|
从找到的这些 Mode* 的乘数分解，可以反推出doom函数输入参数a和b的所有可能取值。
由 cheakkey 函数可知 mode1 和 mode3 相等（都等于int((key[1]/key[-2])*10**16)），因此通过 remembermode[0] 和 remembermode[1] 分别反推出的a和b的可能的取值一定会出现重复值，而这个重复值就是 mode1(mode3)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | def mulall(a):
r = 1
for c in a:
r *= c
return r
rk1 = 30413574359725275612744778689984
rk2 = 49715060849837149374468109364128
possibles1 = {}
for r in selects1:
s = mulall(r)
assert rk1 % s == 0
a, b = s, rk1 // s
possibles1[a+b] = (a, b)
possibles1[a] = (a, b)
possibles1[b] = (a, b)
for r in selects2:
s = mulall(r)
assert rk2 % s == 0
a, b = s, rk2 // s
if a in possibles1:
print("!", a)
if b in possibles1:
print("!!", b)
if a+b in possibles1:
print("!!!", a+b, a, b)
|
经过筛选，发现重复值是唯一的：14109109473780244，这就是 mode1 和 mode3 的值。同时也得到了 mode4 的候选取值： (7281890800772888, 6827218673007356)
获得 mode2 的候选取值：
1 | print(possibles1[14109109473780244])
|
mode2 的候选取值是 (2655331149022192, 11453778324758052)
伍
已知 mode1=int((key[1]/key[-2])*10**16)
注意到：
key[i] = finalkey[i] = Q / keywords1[i]
所以：key[1]/key[-2] = finalkey[1]/finalkey[6] = keywords1[6]/keywords1[1]
即：如果已知 mode*，就可得到相应的两个整数 keywords1 的比值
可以用前面的方法，遍历其中一个的取值，检验另一个是否为整数：
1 2 3 4 5 6 7 8 9 10 11 | mode1 = 14109109473780244
mode2s = (2655331149022192, 11453778324758052)
mode3 = mode1
mode4s = (7281890800772888, 6827218673007356)
for k in [mode1, *mode2s, *mode4s]:
for a in validkeywords1:
b = a * k / 10**16
if abs(b-int(b+0.5)) < 0.00001:
print(a,b)
print()
|
得到的结果：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 3884209 5480273.000004249
5860591 8268772.000005123
8001505 11289411.0
4846066 1286791.0000017378
7468737 1983196.9999954558
3237096 3707697.999996099
3347780 3834473.000005851
10254280 11745025.0
3181316 2171953.999993707
11441028 7811040.0
|
其中引起注意的是精确到整数的几个数：
1 2 3 | 8001505 11289411.0
10254280 11745025.0
11441028 7811040.0
|
经过验证，这6个数都在 validkeywords1 中，它们就是 keywords1 的中间6个值
陆
至此已经获得了 keywords1 的全部8个值。反推输入serial的过程可以直接查表：
1 2 3 4 5 6 7 8 | ans = ""
for n in (9258496, 8001505, 11441028, 10254280, 7811040, 11745025, 11289411, 8343984):
print(n, validkeywords1[n] if n in validkeywords1 else None)
r = validkeywords1[n]
ans += r[0][0]+r[0][1]
print(ans)
|
（多解的问题：ascii 48-51 加上 175 与 123-126 加上 100 是相等的。不过如果输入限定在字母和数字，则只有唯一解）
柒
反推得到的serial输入给程序，直接通过了程序的验证。
（所以程序中关于 Q 的计算完全不用考虑？这也许是出题人给我们的启示：不要过早的陷入复杂的细节中）
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
最后于 2022-6-8 05:42
被mb_mgodlfyn编辑
，原因：
