末两位数（1992）_题解

本文主要是介绍末两位数（1992）_题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题解提供者】吴立强

解法

思路

指数函数增长速率过快，直接计算中间过程任何一种基本类型都无法存储。

通过乘法运算的规律，可以发现末两位数只和末两位数相关，故直接对中间结果保留末两位数（mod 100）即可避免乘法溢出。

代码

#include <iostream>
using namespace std;const int mod = 100;int main() {int n;  cin >> n;int ans = 1;while(n --) ans = (ans * 92) % mod;cout << ans;return 0;
}

算法分析

本算法的时间复杂度为 $O(n)$。

拓展

实际上对于任意的 $(a\times b)\mathrm{mod}p$ 的求解都可以转化为：$((a\mathrm{mod}p)\times (b\mathrm{mod}p))\mathrm{mod}p$。
$a$ 可以看做是 $a=k_1\times p+(a\mathrm{mod}p)$。
$b$ 可以看做是 $b=k_2\times p+(b\mathrm{mod}p)$。
那么有：
$(a\times b)\mathrm{mod}p$
$=((k_1\times p+(a\mathrm{mod}p))\times (k_2\times p+(b\mathrm{mod}p)))\mathrm{mod}p$
$=((k_1\times k_2+k_1\times (b\mathrm{mod}p)+k_2\times (a\mathrm{mod}p))\times p+(a\mathrm{mod}p)\times (b\mathrm{mod}p))\mathrm{mod}p$
$=((a\mathrm{mod}p)\times (b\mathrm{mod}p))\mathrm{mod}p$。

这篇关于末两位数（1992）_题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---