0

HDU5755 Gambler Bo

• q119214252 发布于
• 1300 收藏

题目链接：点击打开链接 题目大意：有一n*m(1

0

快速幂和矩阵快速幂(取模)算法

• q119214252 发布于
• 1098 收藏

对于普通类型的求a^n，我们的求法是不是a*a*a*a....，这样乘以n次，时间复杂度为O(n)，对于普通n比较小的我们可以接受，然而当n比较大的时候，计算就慢了，所以我们就去寻找更快捷的计算方法！ 例如：我们要求2^8，我们通过当为偶数的时候，a^n=(a*a)^(n/2)，当n为奇数时，a^n=a*(a*a)^(n/2)的形式，是不是可以转化为4^4->8^2->64^1，就可以了，2^5...