mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-04 16:12:47 +08:00
43 lines
1.6 KiB
Markdown
Executable File
43 lines
1.6 KiB
Markdown
Executable File
# [372. Super Pow](https://leetcode.com/problems/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
|
||
|
||
这一题需要用到性质三、四。举个例子：
|
||
|
||
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 就结果快速幂求解。
|