【求助】快速幂取模...神犇给我讲讲吧！~！

顶起！！！！！！！！

…首先，a*b mod p=(a mod p)*(b mod p)mod p
然后对于X^k，我们可以先算X^(k div 2)次方
这样每次把K处以2那么效率就是Logk 每次算再平方，如果当前K为奇数，则在乘以X

•快速幂
–对于计算A^N
•如果N是偶数，则A^N= A^(N/2)^2
•如果N是奇数，则A^N= A^(N/2)^2 * A
–对于计算A^(N/2)
•可如上分解
–这样，计算A^N的时间复杂度就降到O(logN)了。

求快速矩阵幂

和常数快速幂类似 建议写非递归
非递归就是把指数转2进制做

-5 根据矩阵的满足结合律，我们把所有的相同矩阵每次分一半，其实和快速幂一样

快速幂就是个二分的思想，通过某种方法实现二分，直接搞也行，矩阵也行

多谢各位、各位RP++，不久后的noip会有回报地> <