快速幂

发布时间：2020-12-13 21:13:13 所属栏目：PHP教程来源：网络整理

导读：题目计算 a n % 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; } i

题目

计算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,n: 32bit integers
     * @return: An integer
     */
    public int fastPower(int a,int n) {
        // write your code here
        if(n==0)
            return 1%b;

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


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

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

class Solution {
    /*
     * @param a,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;
    }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!