Сложность: 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.
😎 Решение:
public class Solution {
public int getSum(int a, int b) {
int x = Math.abs(a), y = Math.abs(b);
if (x < y) return getSum(b, a);
int sign = a > 0 ? 1 : -1;
if (a * b >= 0) {
while (y != 0) {
int carry = (x & y) << 1;
x ^= y;
y = carry;
}
} else {
while (y != 0) {
int borrow = ((~x) & y) << 1;
x ^= y;
y = borrow;
}
}
return x * sign;
}
}Ставь 👍 и забирай 📚 Базу знаний