package leetcode

// 解法一 快速幂 res = res^10 * qpow(a, b[i])
// 模运算性质一：(a + b) % p = (a % p + b % p) % p
// 模运算性质二：(a - b) % p = (a % p - b % p + p) % p
// 模运算性质三：(a * b) % p = (a % p * b % p) % p
// 模运算性质四：a ^ b % p = ((a % p)^b) % p
// 模运算性质五：ab % p = ((a % p) * ( b % p)) % p, 其中 ab 是一个数字，如:2874，98374 等等
// 举个例子
// 12345^678 % 1337 = (12345^670 * 12345^8) % 1337
//				    = ((12345^670 % 1337) * (12345^8 % 1337)) % 1337  ---> 利用性质 三
//				    = (((12345^67)^10 % 1337) * (12345^8 % 1337)) % 1337  ---> 乘方性质
//                  = ((12345^67 % 1337)^10) % 1337 * (12345^8 % 1337)) % 1337  ---> 利用性质 四
//				    = (((12345^67 % 1337)^10) * (12345^8 % 1337)) % 1337  ---> 反向利用性质 三
func superPow(a int, b []int) int {
	res := 1
	for i := 0; i < len(b); i++ {
		res = (qpow(res, 10) * qpow(a, b[i])) % 1337
	}
	return res
}

// 快速幂计算 x^n
func qpow(x, n int) int {
	res := 1
	x %= 1337
	for n > 0 {
		if (n & 1) == 1 {
			res = (res * x) % 1337
		}
		x = (x * x) % 1337
		n >>= 1
	}
	return res
}

// 解法二 暴力解法
// 利用上面的性质，可以得到：a^1234567 % 1337 = (a^1234560 % 1337) * (a^7 % 1337) % k = ((((a^123456) % 1337)^10)% 1337 * (a^7 % 1337))% 1337;
func superPow1(a int, b []int) int {
	if len(b) == 0 {
		return 1
	}
	last := b[len(b)-1]
	l := 1
	// 先计算个位的 a^x 结果，对应上面例子中的 (a^7 % 1337)% 1337
	for i := 1; i <= last; i++ {
		l = l * a % 1337
	}
	// 再计算除去个位以外的 a^y 的结果，对应上面例子中的 (a^123456) % 1337)
	temp := superPow1(a, b[:len(b)-1])
	f := 1
	// 对应上面例子中的 (((a^123456) % 1337)^10)% 1337
	for i := 1; i <= 10; i++ {
		f = f * temp % 1337
	}
	return f * l % 1337
}