CSP-S 提高级 · CSP 2021 提高级第一轮 第 11 题

有如下递归代码

solve(t, n):
  if t=1 return 1
  else return 5*solve(t-1,n) mod n

则 solve(23,23) 的结果为（ ）。

这题看着要算5的22次方，手算肯定崩，但递归展开后就是求5^22 mod 23。看到模数23是个质数，立马想到费马小定理，指数直接减到1，答案秒出。

学生最容易犯的错误就是死磕计算，试图一步步展开5*5*...*5再取模，或者误以为指数是23直接套用定理。还有的是不理解尾递归的本质，把solve(23,23)当成一个复杂的循环去模拟，完全忽略了模运算在每一步都在起作用，导致对最终结果的数量级产生错误直觉。另外，如果没注意到23是质数这个关键条件，就无法使用费马小定理，只能硬算或陷入死胡同。

这道题考什么

这道题核心考查的是递归函数的展开与化简，以及同余运算中费马小定理的应用。命题人特意选了一个看似需要大量乘法运算的递归式，但模数恰好是质数，就是要考察你看到质数模运算时，能不能迅速联想到指数降维的技巧，而不是盲目地按计算器。

概念与命题视角

先拆解一下代码里的逻辑：

solve(t, n):
  if t=1 return 1
  else return 5*solve(t-1,n) mod n

这是一个典型的尾递归。每次调用，t减1，返回值乘5再对n取模。展开几层看看： solve(3, n) = 5 * solve(2, n) mod n = 5 * (5 * solve(1, n) mod n) mod n = 5 * (5 * 1) mod n = 5^2 mod n

以此类推，solve(t, n) 最终就是 5^(t-1) mod n。

命题人挖坑的地方在于：

• 坑1：直接让你算 5^22 mod 23。22次方手工算太累，且容易出错。
• 坑2：很多学生看到模运算，第一反应是“一步步算”，忽略了费马小定理这种数学捷径。
• 坑3：有些同学会误以为指数是 t 而不是 t-1，或者误以为 23 是合数从而不敢用定理。

思考心法：拿到题先想什么？

1. 看结构：递归终止条件是 t=1 返回 1，每次乘 5 再取模。这明显是指数增长。 2. 看数据：t=23，n=23。指数是 22，模数是 23。 3. 联想定理：模数 23 是质数吗？是的。底数 5 和 23 互质吗？是的。 4. 下结论：根据费马小定理，5^(23-1) ≡ 1 (mod 23)。 5. 验证：5^22 mod 23 = 1。

详细推导与计算

第一步：递归展开

从 solve(23, 23) 开始：

• solve(23, 23) = 5 * solve(22, 23) mod 23
• solve(22, 23) = 5 * solve(21, 23) mod 23
• ...
• solve(2, 23) = 5 * solve(1, 23) mod 23
• solve(1, 23) = 1

把这些连起来： solve(23, 23) = 5 * (5 * (5 * ... (5 * 1) ...)) mod 23 = 5^22 mod 23