首页 > itarticle > lintcode第140题

lintcode第140题

admin 1月 18, 2021 0

1. 问题介绍

描述
计算$a^n % b$，其中$a$，$b$和$n$都是32位的非负整数。
样例
例如 $2^{31} % 3 = 2$
例如 $100^{1000} % 1000 = 0$
挑战
$O(log{n})$
原题链接

2. 解题思路

3. 参考代码

class :
    """
    @param a: A 32bit integer
    @param b: A 32bit integer
    @param n: A 32bit integer
    @return: An integer
    """
    def fastPower(self, a, b, n):
        if n == 0:
            return 1 % b 
        ans = 1 
        while n > 0:
            if n % 2 == 1:
                ans = ans * a % b 
            a = a * a % b 
            n = n // 2 
        return ans % b