从‘计算星期几’到‘快速幂取模’：一个NOI/OpenJudge题目的算法升级之路

从暴力迭代到分治优化：快速幂取模算法的竞赛级实现

计算星期几这类看似简单的题目，实际上是算法竞赛中考察模运算与幂运算优化的经典案例。很多初学者会止步于暴力迭代或递归解法，却不知道背后隐藏着更高效的数学工具。本文将带你从零开始，逐步拆解快速幂取模算法的实现细节，并分析其在信息学竞赛中的实战价值。

1. 问题本质与暴力解法分析

题目要求计算a^b mod 7的结果，并根据余数确定星期几。表面看是日期计算问题，实则是考察模运算性质与算法复杂度优化的典型场景。

1.1 基础解法的时间复杂度陷阱

最常见的三种暴力解法都面临相同的性能瓶颈：

// 迭代法示例 int result = 1; a %= 7; for(int i = 0; i < b; ++i) { result = (result * a) % 7; }

这三种方法的时间复杂度都是O(n)，当b达到1e9量级时（竞赛常见数据范围），这类解法必然超时。下表对比了不同解法在1e9次运算时的理论耗时：

提示：现代CPU每秒约可处理3e8次简单运算，O(n)算法在n>1e8时已难以满足竞赛时间限制

1.2 模运算的数学性质应用

解决这类问题的关键在于利用模运算的分配律：

(a * b) mod m = [(a mod m) * (b mod m)] mod m

这使得我们可以在运算过程中随时取模，避免数值溢出。但仅有这个性质还不够，需要结合幂运算的二分特性才能实现质的飞跃。

2. 快速幂算法的数学原理

快速幂算法基于分治思想，将线性计算转化为对数级计算。其核心在于幂运算的二分展开：

2.1 分治策略的数学表达

对于任意正整数b，可以表示为二进制形式。例如b=13，其二进制为1101，那么：

a^13 = a^8 * a^4 * a^1

这种分解使得计算复杂度从O(n)降至O(log n)。具体数学表达为：

a^b mod m = { 1, b == 0 (a^(b/2) mod m)^2 mod m, b为偶数 (a^(b-1) mod m * a) mod m, b为奇数 }

2.2 位运算优化技巧

实际实现时，可以用位运算进一步优化：

int fastPow(int a, int b, int mod) { int res = 1; a %= mod; while(b > 0) { if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }

关键优化点：

• b & 1判断奇偶，替代b % 2
• b >>= 1替代b /= 2
• 累积平方而非线性相乘

3. 算法实现与性能对比

3.1 递归与迭代实现比较

递归实现更直观体现分治思想：

int recursivePow(int a, int b, int mod) { if(b == 0) return 1; long long half = recursivePow(a, b/2, mod); if(b % 2 == 0) return (half * half) % mod; else return (half * half % mod) * (a % mod) % mod; }

但迭代版本通常更优：

• 无函数调用开销
• 无栈溢出风险
• 更利于编译器优化

3.2 性能实测数据

在i7-11800H处理器上测试不同b值时的运行时间(ms)：

4. 竞赛应用与扩展思考

4.1 典型应用场景

快速幂取模算法在竞赛中广泛应用：

• 大数模运算（RSA加密）
• 组合数计算（Lucas定理）
• 矩阵快速幂（动态规划优化）

4.2 常见变种与陷阱

实际比赛中需要注意的细节：

• 模数为1时的特殊情况
• 中间结果可能溢出的处理
• 负数指数的处理技巧

// 处理负指数的扩展版本 int modPow(int a, int b, int mod) { if(mod == 1) return 0; bool isNegative = b < 0; long long res = 1; a = ((a % mod) + mod) % mod; // 处理负底数 b = abs(b); while(b > 0) { if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } if(isNegative) return modInv(res, mod); // 需要预先实现模逆元 return res; }

4.3 与其他算法的结合

快速幂常与其他算法组合使用：

• 费马小定理求模逆元
• 欧拉定理优化指数
• 矩阵快速幂解线性递推

在解决具体问题时，快速幂算法的高效性往往能成为突破性能瓶颈的关键。比如计算斐波那契数列第n项模p的值，结合矩阵快速幂可将复杂度从O(n)降至O(log n)。