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;
}

Новые блоги и статьи Все статьи Все блоги /
[golang] Алгоритм «Хак Госпера» alhaos 17.05.2026 Алгоритм «Хак Госпера» Хак Госпера (Gosper's Hack) — алгоритм нахождения следующего по величине числа с тем же количеством установленных бит. Придуман Биллом Госпером в 1970-х, опубликован в. . .	Рисование бинарного древа до 6-го колена на js, svg. russiannick 17.05.2026 <svg width="335" height="240" viewBox="0 0 335 240" fill="#e5e1bb"> <style> <!]> </ style> <g id="bush"> </ g> </ svg> function fn(){ let rost;/ / высота древа let xx=165,yy=210,w=256;	FSharp: interface of module DevAlt 16.05.2026 Интерфейс модуля F# позволяет управлять доступностью членов, содержащихся в реализации модуля. По-умолчанию все члены модуля доступны: module Foo let x = 10 let boo () = printfn "boo" . . .	Хитросплетение родственных связей пантеона греческих богов. russiannick 14.05.2026 Однооконник, позволяющий узреть и изучить отдельных героев древней Греции. <!DOCTYPE html> <html lang="ru"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible". . .
[golang] Угол между стрелками часов alhaos 12.05.2026 По заданным значениям часа и минуты необходимо определить значение меньшего угла между стрелками аналогового циферблата часов. import "math" func angleClock(hour int, minutes int) float64 { . . .	Debian 13: Установка Lazarus QT5 ВитГо 09.05.2026 Эта инструкция моя компиляция инструкций volvo https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html и его же старой инструкции по установке Lazarus с gtk2. . .	Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .	Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .

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

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

Опции темы