Алгоритм — C ++: Как рассчитать по модулю числа, возведенного в большую степень?

Оценка 10^n mod M:

Что вам нужно Модульное экспонирование. Это может вычислить (a^b)%m в log_2(b)(журнал базы 2).

пример

Допустим, вам нужно вычислить 10^9,

1. Одним из способов является то, что вы последовательно несколько 10, 9 раз.

2. Или используйте подход «разделяй и властвуй».

   10^9 = (10^8)*(10^1)

   10^8 = (10^4)*(10^4) : Нужно ли вычислять 10^4 дважды?

   10^4 = (10^2)*(10^2) : Нужно ли вычислять 10^2 дважды?

   10^2 = (10^1)*(10^1)

   10^1 = (10^1)*(10^0)

   10^0 это базовый случай.

   Итак, что мы в основном делаем:

   1. Если power нечетное число, то мы вычисляем base^(power-1) и умножить это на base получить base^power, [base^power = (base^(power-1)) * base)]
   2. Если power четное число, то мы вычисляем base^(power/2) и умножить его на себя, чтобы получить base^power, [base^power = (base^(power/2)) * (base^(power/2))]. Но мы вычисляем base^(power/2) только однажды.

Вычислительная сложность:

Как указано Вот:

Краткий анализ показывает, что такой алгоритм использует floor(log_2(n)) кварталы и
в большинстве floor(log_2(n)) умножения. Точнее,
количество умножений на единицу меньше числа присутствующих
в двоичном разложении п.

Таким образом, мы можем сказать, что время выполнения имеет порядок log_2(n), (O(log_2(power)))

Оценка по модулю:

Легко заметить, что при вычислении такого большого значения, как 10^(10^18), мы обязаны переполнить даже самый большой из примитивных типов (long long int). И тут входит Модульное Умножение, в соответствии с которым (a * b) % c = ((a % c) * (b % c)) % c, В качестве примечания вы можете не увидеть это правило в использовании, когда смотрите непосредственно на код, но оно используется, если вы оцениваете рекурсивные вызовы.

Задача решена?

Мы предотвращаем переполнение, вычисляя модуль по ходу. Скажем, если мы получили какое-то значение как 10^9 и нам нужно умножить это на себя. Переполнение? Нет, не в этот раз

ans = ((10^9 % 1000000007) * (10^9 % 1000000007)) % 1000000007
ans = 10^18 % 1000000007
ans = 49

Код:

Хотя существует несколько реализаций, вот простая:

const int M = 1e9 + 7;
long long int powxy(long long int x, long long int y) {
if (y == 0) return 1;
if (y%2 == 1) return (x*powxy(x, y-1))%M;
long long int t = powxy(x, y/2);
return (t*t)%M;
}

проверенный Вот.