您当前位置：首页 > php开源 > php教程 > 快速幂

快速幂

来源：程序员人生发布时间：2016-08-08 11:14:53 阅读次数：2212次

题目

计算an%b，其中a，b和n都是32位的整数。

解题

直接求超时

class Solution {
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    public int fastPower(int a, int b, int n) {
        // write your code here
        if(n==0){
            return 1%b;
        }
        int result = 1;
        for(int i=1;i<=n;i++){
            result = result * a%b;
        }
        return result;
    }
};

仿照求幂的方法
result要定义为Long，否则异常使结果毛病

class Solution {
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    public int fastPower(int a, int b, int n) {
        // write your code here
        if(n==0)
            return 1%b;

        if(n==1){
            return a%b;
        }


        long result = fastPower(a,b,n/2);
        result = (result * result)%b;
        if(n%2==1){
            result = result * a%b;
        }
        result = result%b;
        return (int)result;
    }
};

网上看到下面的快幂算法不知道为何出错

class Solution {
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    public int fastPower(int a, int b, int n) {
        // write your code here
        if(n==0)
            return 1%b;

        if(n==1){
            return a%b;
        }

        long res = 1;
        while(n> 0){
            if((n&1)==1)
                res = (res*a)%b;
            n = n>>1;
            a = (a * a)%b;
        }
        return (int)res;
    }
};

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 MyBatis入门第2天--MyBatis与Spring整合及逆向工程

下一篇 python requests模拟登陆github

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点