Задача: 372. Super Pow
Сложность: medium

Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива.

Пример:

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

👨‍💻 Алгоритм:

1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди.

2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337.

3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337.

😎 Решение:

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        MOD = 1337
        
        def powmod(x, y, mod):
            result = 1
            x = x % mod
            while y > 0:
                if y % 2 == 1:
                    result = (result * x) % mod
                y = y // 2
                x = (x * x) % mod
            return result
        
        def superPowHelper(a, b, mod):
            if not b:
                return 1
            last_digit = b.pop()
            part1 = powmod(a, last_digit, mod)
            part2 = powmod(superPowHelper(a, b, mod), 10, mod)
            return (part1 * part2) % mod
        
        return superPowHelper(a, b, MOD)

Ставь 👍 и забирай 📚 Базу знаний