同余问题咨询：刘安迪《算术奇境》中屠龙策略求解

首先明确问题背景：

一条恶龙有$100$个头，只有砍掉所有头才能将其杀死。王子拥有两把剑：长剑每次可精准砍掉$21$个头；短剑每次砍掉$4$个头，但使用后恶龙会立即长出$1985$个头。王子需避免恶龙剩余$1$、$2$或$3$个头，请求解可行的屠龙操作策略。

核心分析：建立数学模型 #

先把每次操作的净头数变化量化：

• 长剑：每次减少$21$个头，净变化为$-21$
• 短剑：砍掉$4$个后长出$1985$个，净变化为$1985-4=+1981$

设王子使用长剑$x$次，短剑$y$次，最终要让恶龙的头数变为$0$，可得到不定方程：

100 - 21x + 1981y = 0

整理后：

21x - 1981y = 100

求解不定方程：判断可行性 #

要判断这个方程是否有整数解，我们需要计算系数的最大公约数（gcd）：

• $1981 = 7 \times 283$
• $21 = 7 \times 3$
• 因此$\gcd(21, 1981) = 7$

观察方程右边的$100$：$100 \div 7 = 14$余$2$，即$100$不是$7$的倍数。而方程左边$21x - 1981y = 7(3x - 283y)$，显然是$7$的倍数。

一个$7$的倍数不可能等于非$7$的倍数，因此这个不定方程没有整数解——也就是说，不存在这样的操作序列，能让王子刚好砍掉恶龙所有的头，同时避免剩余$1$、$2$或$3$个头。

补充验证：操作的实际限制 #

从操作的实际逻辑也能验证这个结论：

• 使用短剑的前提是恶龙当前头数$\geq4$（否则无法砍掉$4$个头），初始$100$满足条件，但每次使用短剑后头数会变为$100 + 1981y$，这个数值可以拆解为$7k + 2$（因为$100=7\times14+2$，$1981y=7\times283y$）。
• 长剑每次砍掉$21$个（$7\times3$），无论砍多少次，剩余头数始终是$7k + 2$的形式，永远无法得到$0$（$0$是$7$的倍数）。

内容的提问来源于stack exchange，提问作者jitender