leetcode-go/medium/372.super-pow.go

func superPow(a int, b []int) int { // Recurse
	n := len(b)
	if n == 0 {
		return 1
	}
	return modPow(superPow(a, b[:n-1]), 10) * modPow(a, b[n-1]) % 1337
}

func modPow(a, b int) (pow int) {
	pow, a = 1, a%1337
	for b != 0 {
		if b&1 == 1 {
			pow = pow * a % 1337
		}
		b >>= 1
		a = a * a % 1337
	}
	return
}

func superPowFP(a int, b []int) int { // Fast power
	pow, n, hi := 1, len(b), 0
	a %= 1337
	for !eq0(b, hi) {
		if b[n-1]&1 == 1 {
			pow = pow * a % 1337
		}
		div2(b, &hi)
		a = a * a % 1337
	}
	return pow
}

func eq0(bn []int, hi int) bool {
	for i := len(bn) - 1; hi <= i; i-- {
		if bn[i] != 0 {
			return false
		}
	}
	return true
}

func div2(bn []int, hi *int) {
	i := *hi
	if bn[*hi] == 1 {
		(*hi)++
	}
	n := len(bn)
	for rem := 0; i < n; i++ {
		num := bn[i] + rem*10
		bn[i], rem = num>>1, num&1
	}
}