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

Новые блоги и статьи Все статьи Все блоги /
Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .	сукцессия 16. Общий обзор, в основном что бы другие ии поняли anaschu 29.06.2026 # Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .	сукцессия 15 неявная схема anaschu 29.06.2026 Алиса Калибровка параметров симбиотической модели: технический обзор Содержание: Введение Постановка проблемы Технические аспекты реализации Процесс внедрения изменений	сукцессия 14. Обновленная схема модели anaschu 28.06.2026 ГЛОБАЛЬНАЯ ОПИСАТЕЛЬНАЯ СПЕЦИФИКАЦИЯ ЭКОСИСТЕМНОЙ МОДЕЛИ «SOIL CHEMISTRY & MYCORRHIZA 2. 0» https:/ / ibb. co/ NnkGpfMd Представленная интегрированная схема описывает непрерывную нелинейную. . .
сукцессия 13. Питон модель трехзонного мицелия, пока что в основном арбускулярного anaschu 28.06.2026 ## Разработка агентной модели микоризной сукцессии: от выявления артефактов к созданию комплексной системы ### Аннотация Представлено исследование по разработке агентной модели микоризной. . .	сукцессия 12. краткий список проверок модели перед запуском. anaschu 27.06.2026 Скрытые отказы в моделях систем динамики (SD-models) экологических систем: два случая из практики Контекст Разбирался прототип модели систем динамики (SD-модели) микоризной сукцессии: пять. . .	Сукцессия 11. Проверка орудий перед войной: разработка через тестирование anaschu 27.06.2026 Как не дать модели соврать самой себе: проверки для симуляции микоризной сукцессии Введение Когда вы строите математическую модель живой системы — грибов, растений, почвы — главная опасность. . .	10 сукцессия. Питон код войны грибов и растений anaschu 27.06.2026 import numpy as np class PlantAgent: def __init__(self, name, strategy, initial_biomass): self. name = name self. strategy = strategy # "greedy" (широколиственные) или. . .

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

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