Как возвести число в квадрат в visual studio

Обновлено: 07.07.2024

Здравствуйте, сегодня поговорим об алгоритме быстрого возведения в степень по модулю, а также реализуем этот алгоритм на C++ под Visual Studio.

Общая информация

Постановка задачи

А что если увеличить числа, например, 5 100 mod7, калькулятором не получится воспользоваться, так как не удастся вычислить 5 100 . Поэтому, можно воспользоваться алгоритмом быстрого возведения в степень.

Суть алгоритма

Чтобы вам было лучше понятно, суть алгоритма мы покажем на 2 примерах, надеюсь, после которых все будет понятно:

1 пример: 5 100 mod7
Напомню общий вид выражения: a x modp

Пойдем по шагам:

Шаг 1
Перевести степень числа из десятичной в двоичную систему исчисления.
100₁₀ = 1100100₂

Шаг 2
Определить число элементов n, которое равно количеству всех цифр степени в двоичной системе.
У нас число 1100100₂ , n = 7 (всего цифр).

Дополнение к шагу 2
В общем виде, число n = [log₂x] + 1 , [] скобки означают, что нужно взять целую часть от числа.
Для нашего примера n = [log₂100] + 1 = 6 + 1 = 7.

В нашей задачи массив будет таким:
massive[0] = 5;
massive[1] = 25mod7 = 4;
massive[2] = 16mod7 = 2;
massive[3] = 4mod7 = 4;
massive[4] = 16mod7 = 2;
massive[5] = 4mod7 = 4;
massive[6] = 16mod7 = 2;

Шаг 4
Вычислить произведение элементов массива, которые возведены в соответствующие степени из двоичной записи числа на 1 шаге.
Нам нужно каждый элемент массива возвести в степень (либо в первую, либо в нулевую), затем перемножить, то что получилось. Самое важное, что возводить нужно по следующему правилу:
1 элемент массива возводится в степень последней цифры двоичного числа, 2 элемент массива возводится в степень предпоследней цифры двоичного числа и так далее.
В нашей задаче: 5 0 * 4 0 * 2 1 * 4 0 * 2 0 * 4 1 * 2 1 = 16

Шаг 5
Вычислить остаток от деления полученного произведения.
16mod7 = 2.
Это значит, что наша задача 5 100 mod7 = 2.

Теперь разберем второй пример, но уже коротко.

2 пример: 3 90 mod5

Шаг 1
90₁₀ = 1011010₂

Шаг 2
n = 7

Шаг 3
massive[0] = 3;
massive[1] = 9mod5 = 4;
massive[2] = 16mod5 = 1;
massive[3] = 1mod5 = 1;
massive[4] = 1mod5 = 1;
massive[5] = 1mod5 = 1;
massive[6] = 1mod5 = 1;

Шаг 4
3 0 * 4 1 * 1 0 * 1 1 * 1 1 * 1 0 * 1 1 = 4

Шаг 5
4mod5 = 4
3 90 mod5 = 4

Реализация задачи на C++

Ну а теперь мы напишем алгоритм быстрого возведения в степень на языке C++ под Visual Studio.

Сначала объявляем переменные, необходимые для алгоритма, а затем осуществляем перевод из десятичной системы в двоичную и считываем в переменную n количество цифр в двоичной записи.

Сначала заполняем наш массив, вычисляя последовательно элементы. Затем вычисляем произведение и остаток от деления.

Читайте также: