CSP-S 2021 第一轮 第11题：有如下递归代码

题目

有如下递归代码

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

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

选项

• A. 1
• B. 7
• C. 12
• D. 22

答案

A

题解

答案是 A. 1。

solve(1, n)=1，之后每递归一层，就乘一次 5 并对 \(n\) 取模，所以 \[ \operatorname{solve}(t,n)=5^{t-1}\bmod n. \] 因此题目要求的是 \(5^{22}\bmod 23\)。

根据费马小定理：若 \(p\) 是质数，且 \(a\) 不是 \(p\) 的倍数，则 \[ a^{p-1}\equiv1\pmod p. \] 因为 23 是质数，5 不是 23 的倍数，所以 \[ 5^{22}\equiv1\pmod{23}. \]

注意：从 \(t=23\) 到 \(t=1\)，一共乘了 22 次 5。