372. Super Pow

问题

　　Your task is to calculate a^b mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

　　Example1:

　　a = 2

　　b = [3]

　　Result: 8

　　Example2:

　　a = 2 　　b = [1,0] 　　Result: 1024

分析
　　
　　根据公式 ① ② a^b mod 1337 可以优化为 (a mod 1337)^bmod 1337 ，所以每次计算底数的时候,计算之前和之后，都进行mod，预防结果超过整数范围。
　　根据公式 ③ ，可以根据题意对指数进行分解，本题的进制为10.
　　根据公式 ④，对计算过程进行分解，每一步都是计算，由于ai知道，所以每步的计算其实是计算底数。

代码　

    int mod = ;

    int superPow(int a, vector<int>& b) {

        int answer = ,n = b.size();

        if( n == )

            return ;

        for(int i = n - ;i >= ; i--)

        {

            if( b[i] > )

                answer = answer * Inpow(a,b[i]) % mod;

            a = Inpow(a,);

        }

        return answer;

    }

    int Inpow(int base,int exp){

        int result = ;

        base = base%mod;

        for(int i = exp; i > ;i = i >> )

        {

            if( i &  == )

                result = result * base %mod;

            base = base * base % mod;

        }

        return result % mod;

    }

巴特西

372. Super Pow

最新文章

热门文章