Сложность: 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 {
func getSum(_ a: Int, _ b: Int) -> Int {
var x = abs(a), y = abs(b)
if x < y {
return getSum(b, a)
}
let sign = a > 0 ? 1 : -1
if a * b >= 0 {
while y != 0 {
let carry = (x & y) << 1
x ^= y
y = carry
}
} else {
while y != 0 {
let borrow = ((~x) & y) << 1
x ^= y
y = borrow
}
}
return x * sign
}
}Ставь 👍 и забирай 📚 Базу знаний