经过抽象并推广的谜题模型
谜题
是整数变量(模 剩余类)。 为 个操作,操作 使 数值分别增加 。 (模 意义下)
给定 的初始值,试求有限的操作序列使 变为同一个数。(模 意义下)
解法
由加法交换律,操作的顺序并不影响结果。设 分别进行了 次,则 变为 , , ,即
其中 , 不妨将操作 记为向量 则
变形得到
这是一个模 意义下的线性方程组。我们只要给出一个解就解决了问题。
如果 为质数,则除 以外都有数论倒数。任取符合要求(即所有数相等)的 ,使用高斯消元法即可解决问题。
为质数的幂时,设 ,作高斯消元法,当进行到某一列时,若对角线元素无数论倒数(即有因子 ),则在下方将被消除的元素中找到与 互质的元素,两者所在两行交换,便可正常进行消元。若所有将被消除 的元素中均是 的倍数,则选取因子 的次数最小的元素与原来的对角线元素所在两行对换,消元可正常进行。
为一般合数时,分解为不同质数的幂相乘的形式,分别改写成模不同质数的幂的线性方程组的形式并解之,最后用中国剩余定理合并解即可。
不为质数的情况任选 可能无解,因此需要枚举 个 来寻找解。若 较大,计算上建议记录高斯消元法的步骤(表示为左乘原系数矩阵的矩阵)。
应用于原神解谜
原神中相关谜题之于上述模型是特例中的特例,虽然简单但也正是这些谜题引出了上述问题与思考。
如图谜题,即对其中某一方块,攻击之可改变自己和其余方块上的数字(以模加法的形式),原神中应该都具体为自己和相邻方块数字+1。解密目标为通过一连串攻击操作使所有方块数字相同。
游戏内另有一类解密与此方块相同,但攻击是改变朝向,目标为所有方块朝向一致,与上述数字型解密内核相同。数字型是模 ,朝向型是模 ,即 或 。
对于有 个方块的谜题, 个方块上现有的数字即为 。 个方块正对应 个操作,可按照操作的影响写出矩阵 。解方程组得到答案。
以图中谜题为例, ,此处模数为质数,故 可任取,这里取 。
得到方程
给出一个解:,即攻击最左边的方块两次,最右边的两个方块分别一次即可。