0372. Super Pow

372. Super Pow #

题目 #

Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example 1:

Input: a = 2, b = [3]
Output: 8

Example 2:

Input: a = 2, b = [1,0]
Output: 1024

题目大意 #

你的任务是计算 a^b 对 1337 取模,a 是一个正整数,b 是一个非常大的正整数且会以数组形式给出。

解题思路 #

  • 求 a^b mod p 的结果,b 是大数。

  • 这一题可以用暴力解法尝试。需要用到 mod 计算的几个运算性质:

      模运算性质一:(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  ---> 反向利用性质 三
    

    经过上面这样的变换,把指数 678 的个位分离出来了,可以单独求解。继续经过上面的变换,可以把指数的 6 和 7 也分离出来。最终可以把大数 b 一位一位的分离出来。至于计算 a^b 就结果快速幂求解。

代码 #


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
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者