快速幂
快速幂取模
用法:用于求解 a 的 b 次方,而b是一个非常大的数,用O(n)的复杂度会超时。但是这个算法的时间复杂度是O(log n).
1 int pow_mod(int a, int b, int c)//a^b%c; 2 { 3 int ans = 1; 4 a = a%c; 5 while (b > 0) 6 { 7 if (b % 2 == 1) 8 { 9 ans = (ans*a) % c; 10 } 11 b = b / 2; 12 a = (a*a) % c; 13 } 14 return ans; 15 }
那么假如让你求一个矩阵的很大的次方幂呢,当然我们同样可以求解。
可以参考dalao的博客:
http://blog.csdn.net/y990041769/article/details/22311889