FJUT寒假作业第二周G题解快速幂
题目来源：http://210.34.193.66:8080/vj/Contest.jsp?cid=161#P6
题意：求n个数字的乘积对c取摸。主要就是有快速幂扩展到广义幂的过程。
首先题目几个可能看不懂的地方。 n>>=1 -> n=n>>1 按位右移一位 相当/2； 然后 n&1 相当于n%2 可推广到 n% (2<<n) 和 n&( (2<<n) -1)等价。
算a^4=a*a*a*a 四次运算 而如果 a=a*a a=a*a 利用循环跌倒可以减少运算次数。乘法与加法同理，这里^是次方，不是异或。
然后理解快速幂的过程。 a^13=(a^6)^2*a
a^6=(a^3)^2
a^3=(a^2)*a 这样比较好理解快速幂为什么 指数n为奇数的时候*temp, 而又每次都要 temp=temp*temp.每次n>>=1
类比加法； a*13=a*6*2+a
a*6=a*3*2
a*3=a*2+a 这样就更好的理解广义幂，对应下面代码理解下为什么奇数+a,
理解了原理这一题我们就可以轻松写出广义幂了。
凡岛公司福利 674人发布