【解题报告】快速幂 Fast Power

题目地址

http://www.lintcode.com/en/problem/fast-power/

题目大意

计算a^n%b

思路

关于数值范围的优化

看起来很简单的题目，但是如果直接去求解的话，当n足够大的时候，a^n会很大，超出了表达范围 这适合我们需要深入的研究取模运算的规律了 这里我们主要使用了模运算的一个性质 (ab)%c = (a%c)(b%c)%c 通过这样的分解我们就可以避免由于中间数值过大而造成无法表达的情况了

关于时间性能的优化

优化完了表达范围的问题，我们还面临另一个问题，那就是，当n很大的适合，如果我们每次都去执行的话，复杂度是O(n) 这是可以进一步优化的 考虑分解n，可以表示为二进制，而通过二进制我们就可以表示为0或者1的2的次幂。 例如，5，二进制表达为101，即，1的2^2次幂+0的2^1次幂+1的2^1次幂 对于0为底数的情况,我们可以忽略,因为任何数的0次方为1,1乘以任何数还是本身,不会对取模运算造成影响 所以,当该位为1的时候,我们就可以进行一次运算 我们知道,当一个数的二进制最低位为1,那么它就是个奇数,所以我们每次操作后对n右移一位,判断是不是奇数 这样,我们需要执行的操作数量就是logn了,大大优化了时间复杂度从O(n)到了O(logn)

代码

public int fastPower(int a, int b, int n) {
        // write your code here
           if(n == 0)return 1%b;
      long ret=1;
        long tmp=a;
        while(n > 0)
        {
            if(n%2 == 1)//判断是否为奇数,确定末位是不是为1
                ret=ret*tmp%b;//运算余数

            tmp = tmp*tmp%b;//累乘

            n>>=1;//右移一位,相当于除以2
        }
        return (int)ret;
    }

总结

在做这道题的时候,当时以为很简单,但是其中用到的公式和规律,没有一定的了解自己去研究还是需要很久的,以前做题总是觉得自己想出来才算厉害,但是并不是这样,当面对能力外的题目的时候,不妨先看看别人如何解. 当看过之后,深入理解别人的解法,分析为什么这样做,然后在自己解的过程中,充分理解,这样,做了这道题就算有所收获.