Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.96
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
#1

A^B mod C - C++

06.08.2011, 20:50. Просмотров 3186. Ответов 22
Метки нет (Все метки)

Найти A^B mod C. Тут как-то надо использовать рекурсию. Кто может помочь?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.08.2011, 20:50
Здравствуйте! Я подобрал для вас темы с ответами на вопрос A^B mod C (C++):

mod - C++
Здравствуйте! У меня вопрос наверное глупый. Препод для выбора курсовой поставил следующие условия: Вариант задания выбирается по формуле...

mod (на C) - C++
нужно проверить число на нечётность я сделал так: if (k mod 2 == 1) <действия> но компилятор выдал ошибку типа:syntax error...

div и mod - C++
Помогите, пожалуйста: вводимое с клавиатуры число n нужно разделить следующим образом (n, n1, n2 - целые ): если n четное, то n1 = n2 =...

DIv MOD в С++ - C++
не подскажете как описать оператор ДИВ в С++? суть такова а=5 b=2 x=a DIV 2 y=5/2 printf(...x) (y) мне нужно...

mod и div - C++
вообщем задачка такая. Нужно вычислить сумму средних чисел четырёхзначного числа. На паскале проблем не возникло, а вот С++ постоянно...

mod и div ?? - C++
Подскажите пожалуйста как будет mod и div в С++? Очень нужно)) Добавлено через 9 минут и пожалуйста напишите пример как...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
07.08.2011, 00:10 #16
если ^ все-таки возведение в степень, то используется модулярная арифметика. возведение A в степень B по модулю C это повторяющееся умножение A на A по модулю С B раз. А умножение по модулю C это повторяющееся сложение A и A по модулю С.

если в коде, A,B и С большие положительные числа:

сложение по модулю (т.е. получаем именно (A+B)%C)
C++
1
2
3
4
long long int addition (long long int A, long long int B, long long int C) {
if (C-A<B) return ((((A>>1)+(B>>1))%(C>>1))<<1)+(A&1)+(B&1)-(C&1);
return (A+B)%C;
}
умножение по модулю:
C++
1
2
3
4
5
6
7
8
9
long long int mulptiplication (long long int A, long long int B, long long int C) {
long long int remainder = 0;
while (B) {
  if (B&1) remainder=addition(A,remainder,C);
  A=addition(A,A,C);
  B>>=1;
}
return remainder;
}
возведение в степень по модулю:
C++
1
2
3
4
5
6
7
8
9
10
long long int power (long long int A, long long int B, long long int C) {
long long int remainder = 1;
if (!B) return -1;
while (B) {
  if (B&1) remainder=multiplication(A,remainder,C);
  A=multiplication(A,A,C);
  B>>=1;
}
return remainder;
}
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
07.08.2011, 09:38  [ТС] #17
grizlik78, да нет, unsigned long long переименовал переменные просто, на больших не заработал... придётся длинную арифметику делать. А за код спасибо)
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
07.08.2011, 11:38 #18
Все работает, даже 2^63

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 *= deg;
         rez %= c;
      }
      deg *= deg;
      deg %= c;
      b >>= 1;
   }
   return rez;
}
Если модуль c не нужен, удалите строки

unsigned long c
rez %= c;
deg %= c;

Добавлено через 34 минуты
Если модуль c не больше 2^64-1, то этим алгоритмом можно вычислять хоть числа 500^10000 mod 12345, 2^12356789 mod 100000 и т.д.
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
07.08.2011, 12:24  [ТС] #19
Olga_, спасибо, теперь то хоть вместо Ошибка выполнения, Неверный ответ пишет... Значит уже пошло дело к лучшему...
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
07.08.2011, 12:43 #20
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Olga_, спасибо, теперь то хоть вместо Ошибка выполнения, Неверный ответ пишет... Значит уже пошло дело к лучшему...
Как это, а вы на чем тестировали?

Добавлено через 11 минут
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
#include <cstdlib>
#include <iostream>
#include <clocale>
using namespace std;
 
 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 *= deg;
         rez %= c;
      }
      deg *= deg;
      deg %= c;
      b >>= 1;
   }
   return rez;
}
 
int main(int argc, char* argv[])
{
   cout << Degree(2, 63, 1 << 64 - 1);
   getchar();
   return 0;
}
grizlik78
Эксперт С++
1908 / 1440 / 111
Регистрация: 29.05.2011
Сообщений: 2,996
07.08.2011, 14:18 #21
Цитата Сообщение от 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
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
07.08.2011, 14:31 #22
Цитата Сообщение от AvengerAlive Посмотреть сообщение
придётся длинную арифметику делать
При больших a и b у вас ответ в памяти не поместится. Да и считать ваша программа будет ну очень долго. Ява с ее BigInteger'ом и бинарным возведением в степень виснет уже примерно на а = 10^8 b = 10^7.
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
07.08.2011, 15:40 #23
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;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.08.2011, 15:40
Привет! Вот еще темы с ответами:

Div и mod в С++ - C++
Здравствуйте. Перехожу из паскаля в c++. Есть отрывок кода который проверяет есть ли в числе N цифра 3 и есть ли в числе вводимое с...

Операция mod() - C++
Подскажите, pls, как осуществить операцию m mod n (вычисление остатка) не используя операцию деления в процессе вычисления?

mod и div (Чистый С) - C++
Здравсвтуйте,как на чистом С описывать эти функции mod и div????

Что такое mod в с++ ? - C++
что такое mod в с++ и как он работает? например, m=12*17^9 mod 23. (m должно получиться 15)


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
07.08.2011, 15:40
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru