A^B mod C

@AvengerAlive · Регистрация: 30.07.2011

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

Найти A^B mod C. Тут как-то надо использовать рекурсию. Кто может помочь?

@grizlik78 · 07.08.2011, 14:18

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

grizlik78, да нет, unsigned long long переименовал переменные просто, на больших не заработал... придётся длинную арифметику делать. А за код спасибо)

Ещё раз: я создавал эту функцию исходя из условия, что все операнды не больше 32 бит. Просто изменить тип переменных, разумеется, нельзя, потому что unsigned long long тогда придётся заменить на какой-нибудь 128-битный тип.

Общий подход показал Paporotnik. В принципе, на основе моей функции тоже можно реализовать умножение по модулю, заменив * на +. Но надо чётко представлять где какой размер возможен у операндов и результатов.

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

Если модуль c не больше 2^64-1, то этим алгоритмом можно вычислять хоть числа 500^10000 mod 12345, 2^12356789 mod 100000 и т.д.

Нет. Например 1000000000^1000000000 mod 9876543210 будет вычислено неправильно. То есть сам алгоритм правильный, но в данной реализации ответ будет неверным. Правильный ответ 7829903980

@diagon · 07.08.2011, 14:31

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

придётся длинную арифметику делать

При больших a и b у вас ответ в памяти не поместится. Да и считать ваша программа будет ну очень долго. Ява с ее BigInteger'ом и бинарным возведением в степень виснет уже примерно на а = 10^8 b = 10^7.

@Olga_ · 07.08.2011, 15:40

64 бита не обещаю, но диапазон шире в такой реализации

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdlib>
#include <iostream>
#include <clocale>
using namespace std;
 
unsigned long long Multiple(unsigned long long a, unsigned long long b, unsigned long long c)
{
   unsigned long long deg = b, rez = 0;
   while (a)
   {
       if (a & 1)
       {
          rez += deg;
          rez %= c;
       }
       a >>= 1;
       deg <<= 1;
       deg %= c;
   }
   return rez;
 
}
 
unsigned long long Degree(unsigned long long a, unsigned long long b, unsigned long long c)
{
   unsigned long long deg, rez;
   rez = 1;
   deg = a;
   while (b)
   {
      if (b & 1)
      {
         rez = Multiple(rez, deg, c);
         rez %= c;
      }
      deg = Multiple(deg, deg, c);
      deg %= c;
      b >>= 1;
   }
   return rez;
}
 
int main(int argc, char* argv[])
{
   cout << Degree(1000000000, 1000000000, 9876543210) << endl;
   getchar();
   return 0;
}

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257

	A^B mod C 06.08.2011, 20:50. Показов 13359. Ответов 22 Метки нет (Все метки) Найти A^B mod C. Тут как-то надо использовать рекурсию. Кто может помочь? 0