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

A^B mod C - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.96
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
06.08.2011, 20:50     A^B mod C #1
Найти A^B mod C. Тут как-то надо использовать рекурсию. Кто может помочь?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.08.2011, 20:50     A^B mod C
Посмотрите здесь:

mod (на C) C++
C++ mod и div
C++ Операция mod()
mod и div ?? C++
div и mod C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Roof
 Аватар для Roof
154 / 154 / 10
Регистрация: 03.11.2010
Сообщений: 393
06.08.2011, 21:34     A^B mod C #2
Рекурсию нужно использовать при возведении в степень.
Насколько я понял эту запись, то сначала A возводится в степень B, потом от полученного результата находим остаток от деления на C.
Один из самых простых вариантов, работает только со степенями >= 0.
Есть такая оговорка: если один из операндов оператора % ( остаток от деления ) отрицательный, то результат получится зависимый от машины.
Т.е. нужно предусматривать:
- чтобы либо все числа A, B и C были положительными,
- либо если число A отрицательно, то степень B должна быть четная и число C положительно
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
#include <iostream>
using namespace std;
 
int pow_xy( int x, int y ) {
    if ( y == 0 )
        return 1;
    else
        return x * pow_xy( x, y - 1 );
}
 
int main() {
    int a, b, c;
    cout << "Введите a" << endl;
    cin >> a;
 
    cout << "Введите b" << endl;
    cin >> b;
 
    cout << "Введите c" << endl;
    cin >> c;
 
    cout << "Результат: " << ( pow_xy( a, b ) %c ) << endl;
    return 0;
}
CAHTEXHUK
Заблокирован
06.08.2011, 21:36     A^B mod C #3
я думал ^ это xor o_0
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.08.2011, 21:38     A^B mod C #4
Цитата Сообщение от Roof Посмотреть сообщение
Рекурсию нужно использовать при возведении в степень.
Насколько я понял эту запись, то сначала A возводится в степень B, потом от полученного результата находим остаток от деления.
Один из самых простых вариантов, работает только со степенями >= 0.
Есть такая оговорка: если один из операндов оператора % ( остаток от деления ) отрицательный, то результат получится зависимый от машины.
Т.е. нужно предусматривать:
- чтобы либо все числа A, B и C были положительными,
- либо если число A отрицательно, то степень B должна быть четная и число C положительно
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
#include <iostream>
using namespace std;
 
int pow_xy( int x, int y ) {
    if ( y == 0 )
        return 1;
    else
        return x * pow_xy( x, y - 1 );
}
 
int main() {
    int a, b, c;
    cout << "Введите a" << endl;
    cin >> a;
 
    cout << "Введите b" << endl;
    cin >> b;
 
    cout << "Введите c" << endl;
    cin >> c;
 
    cout << "Результат: " << ( pow_xy( a, b ) %c ) << endl;
    return 0;
}
a = 1000, b = 10000 ?
Могу ошибаться, но тут нужно хранить в А только последние n чисел, n зависит от C(количество разрядов в С + 1).
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
06.08.2011, 21:41     A^B mod C #5
если погуглить, то поятно, что задача олимпиадная и идет речь об математической закономерности
задача дается на большие числа
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
06.08.2011, 21:42  [ТС]     A^B mod C #6
Roof, A,B,C<10^9 как возводить то?
Roof
 Аватар для Roof
154 / 154 / 10
Регистрация: 03.11.2010
Сообщений: 393
06.08.2011, 21:44     A^B mod C #7
2 CAHTEXHUKну - да, это xor, а я поторопился.
2 AvengerAlive - я решил, что это простая задачка учебная, которая ограничивается небольшими числами, но, видимо, ошибся.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
06.08.2011, 21:45     A^B mod C #8
Roof,
Цитата Сообщение от alex_x_x Посмотреть сообщение
адача олимпиадная и идет речь об математической закономерности
Roof
 Аватар для Roof
154 / 154 / 10
Регистрация: 03.11.2010
Сообщений: 393
06.08.2011, 21:50     A^B mod C #9
2 alex_x_x - нагуглил, увидел, спасибо.
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
06.08.2011, 21:52  [ТС]     A^B mod C #10
CAHTEXHUK, ^ возведение в степень не в С

Roof, лонг лонг заработал только ошибку даёт на больших значениях
Roof
 Аватар для Roof
154 / 154 / 10
Регистрация: 03.11.2010
Сообщений: 393
06.08.2011, 22:01     A^B mod C #11
2 AvengerAlive - мой алгоритм неверен для больших чисел.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
06.08.2011, 22:13     A^B mod C #12
Вот, переделал из обычного возведения в степень, надеюсь ничего лишнего не выкинул в процессе.
Идея в том, чтобы представить возведение в степень в виде возведений в квадрат и умножений на основание. Например
http://www.cyberforum.ru/cgi-bin/latex.cgi?5^{11} =  5\Bigl(5\bigl(5^2\bigr)^2\Bigr)^2
Операцию приведения по модулю надо выполнять после каждой промежуточной операции, чтобы не возникало переполнения.
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
#include <stdio.h>
 
unsigned pow(unsigned a, unsigned b, unsigned m)
{
    unsigned n = 0;
    unsigned k = 1;
    unsigned long long res;
    if (0 == a)
        return 0;
    if (0 == b)
    return 1;
 
    while ( (n = k << 1) <= b && n )
        k = n;
    if (0 == n)
        return 0;
    res = a;
    k >>= 1;
    while (k)
    {
        res = (res*res) % m;
        if (k & b)
            res = (res*a) % m;
        k >>= 1;
    }
    return (unsigned)(res);
}
 
int main()
{
    unsigned a;
    unsigned b;
    unsigned m;
    scanf("%u%u%u", &a, &b, &m);
    printf("%u**%u mod %u = %u\n", a, b, m, pow(a, b, m));
    return 0;
}
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
06.08.2011, 22:22     A^B mod C #13
чегото вроде
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
 
unsigned f( unsigned a, unsigned now_b, unsigned c )
{
   std::cout << a << " " << now_b << std::endl;
   switch( now_b )
   {
     case 1: return a;
     case 2: return a*a;
     default: 
     {
        unsigned  left_b_power = now_b / 2, 
                  right_b_power = now_b - left_b_power;
        return f( a, left_b_power, c ) * f( a, right_b_power, c ) % c;
     }
   }
}
 
int main()
{
   std::cout << f( 15, 15, 34 );
}
это по свойству (A*B) mod C = ((A mod C)*(B mod C)) mod C

Добавлено через 6 минут
долговато на больших числах выходит
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
06.08.2011, 22:53  [ТС]     A^B mod C #14
grizlik78, спасибо, тесты 2^31 прошёл, а вот 2^63 под unsigned long long уже не получается...
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
06.08.2011, 22:55     A^B mod C #15
AvengerAlive, в смысле если операнды 63 бита длиной? так я этого не обещал.
Когда показания на ходу меняются — я так не играю
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Roof, A,B,C<10^9 как возводить то?
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
07.08.2011, 00:10     A^B mod C #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  [ТС]     A^B mod C #17
grizlik78, да нет, unsigned long long переименовал переменные просто, на больших не заработал... придётся длинную арифметику делать. А за код спасибо)
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
07.08.2011, 11:38     A^B mod C #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  [ТС]     A^B mod C #19
Olga_, спасибо, теперь то хоть вместо Ошибка выполнения, Неверный ответ пишет... Значит уже пошло дело к лучшему...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.08.2011, 12:43     A^B mod C
Еще ссылки по теме:

C++ mod
DIv MOD в С++ C++
Div и mod в С++ C++

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

Или воспользуйтесь поиском по форуму:
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
07.08.2011, 12:43     A^B mod C #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;
}
Yandex
Объявления
07.08.2011, 12:43     A^B mod C
Ответ Создать тему
Опции темы

Текущее время: 19:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru