快速幂取模算法 | 一瓜算法小册

[Desgard]

https://www.desgard.com/algo/docs/part2/ch01/2-quick-pow-mod/

快速幂取模算法

[wuxiangjinxing]

以下代码TLE了，能否请帮忙指点一下应该如何优化？非常感谢。 很抱歉我实在搞不懂如何在这里正确显示缩进，用``的话整个代码都会缩成一行。如果看不清楚的话可以看这里： https://docs.google.com/document/d/1N3HKnXOCodzWyg8hag9kRriD6k_kGsFIEf7hD6HNi9k/

def superPow(self, a: int, b: List[int]) -> int:
    res = 1
    ind = 1
    for i in range(len(b) - 1, -1, -1):
        v = b[i] * ind
        x = a
        while v > 0:
            if v & 1:
                res *= x
                res %= 1337
            x *= x
            x %= 1337
            v >>= 1          
        ind *= 10
    return res % 1337