LeetCode //C - 372. Super Pow

372. Super Pow

Your task is to calculate $a^b$ 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

Example 3:

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

Constraints:

• $1<=a<=2^{31}-1$
• 1 <= b.length <= 2000
• 0 <= b[i] <= 9
• b does not contain leading zeros.

From: LeetCode
Link: 372. Super Pow

---

Solution:

Ideas:

1. powMod Function: This function computes $a^k$ mod mod using an iterative method to efficiently handle large exponents.

2. superPow Function:

• We initialize result to 1.
• For each digit in b:
  • Update result to $resul{t}^{10}$ mod1337 because each new digit shifts the previous result to the next power of 10.
  • Multiply by $a^{b[i]}$ mod1337 to account for the current digit.
• Use the modulo operation to keep numbers manageable and avoid overflow.

Code:

int powMod(int a, int k, int mod) {
    long long result = 1;
    long long base = a % mod;
    while (k > 0) {
        if (k % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        k /= 2;
    }
    return (int)result;
}

int superPow(int a, int* b, int bSize) {
    const int MOD = 1337;
    int result = 1;
    for (int i = 0; i < bSize; i++) {
        result = powMod(result, 10, MOD) * powMod(a, b[i], MOD) % MOD;
    }
    return result;
}

原文地址：https://blog.csdn.net/navicheung/article/details/142298688

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！