372. 超级次方

解题思路

迭代法求Pow + 递推求superPow
注意Pow处要对a做mod c操作

代码

func Pow(a, b, c int) int {
    result := 1
    for ;b>0;a=a*a%c{
        if b&1==1{  // 位运算优化
            result = result * a 
            result %= c
        }
        b=b>>1
    }
    return result
}

func superPow(a int, b []int) int {
    const c = 1337

    if len(b)==1{
        return Pow(a, b[0], c)
    }

    result := 1
    an := a
    for i:=len(b)-1;i>-1;i--{
        result = result * Pow(an, b[i], c) % c
        an = Pow(an, 10, c) 
    }
    return result % c
}