Быстрое возведение в степень

@Senarist · Регистрация: 14.03.2014

Студворк — интернет-сервис помощи студентам

Хочу реализовать быстрое возведение в степень, но проблема в том что то число которое возводим в степень записано не в какой нибудь базовой переменной, а в массиве (по одной цифре, т.к. оно может быть очень большим). Как это дело перевести в двоичную систему?

@SerVal · 25.03.2017, 11:51

Сообщение от Senarist

Как это дело перевести в двоичную систему?

Что значит "перевести в двоичную"? В двоичной системе число будет ещё длиннее.
И для его хранения тоже понадобится массив или вектор.
*****
Напишите пока быстрое возведение в степень обычного числа.
Можно ещё взять длинную арифметику( из буста, например).

@Senarist · 25.03.2017, 12:38 **[ТС]**

SerVal ну это в свободном доступе есть:

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
using namespace std;
 
int main()
{
    setlocale(LC_ALL, "Russian");
    int a(70), x(8), p(36), i(0);
    int vi = x; // переменная для вывода на экран
 
    int x2[30]; // создаем одномерный массив для
    while (x >= 1) // перевода в двоичную систему исчисления
    {
        x2[i] = x % 2;
        x /= 2;
        i++;
    }
    int n = i; // запоминаем количество цифр
 
    int *arr = new int[n]; // массив значений
    arr[0] = a; // 1 элемент
    for (int i = 1; i < n; i++) {
        arr[i] = (arr[i - 1] * arr[i - 1]) % p;
    }
    int proizv = 1;
    for (int j = 0; j < n; j++) {
        if (x2[j] > 0) {
            proizv *= x2[j] * arr[j];
        }
    }
    cout << "Остаток от деления " << a << "^(" << vi << ")mod" << p << " равен: " << proizv%p << endl;
    delete[] arr;
    cin.get();
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .

@Senarist 58 / 62 / 34 Регистрация: 14.03.2014 Сообщений: 933

	Быстрое возведение в степень 25.03.2017, 10:45. Показов 2824. Ответов 2 Метки нет (Все метки) Хочу реализовать быстрое возведение в степень, но проблема в том что то число которое возводим в степень записано не в какой нибудь базовой переменной, а в массиве (по одной цифре, т.к. оно может быть очень большим). Как это дело перевести в двоичную систему? 0

Быстрое возведение в степень

Решение