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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
roanna
16 / 16 / 2
Регистрация: 11.11.2010
Сообщений: 88
#1

Быстрый подсчет A^B mod C или "Алгоритм русского крестьянина" - C++

12.03.2013, 20:58. Просмотров 1359. Ответов 4
Метки нет (Все метки)

Нужно максимально быстро посчитать A^B mod C. Написала алгоритм, казалось бы все хорошо, да вот только сижу я на e-olimp'e, делаю задачки, а ему не нравится. Последние несколько тестов не проходит, пишет "неправильный ответ". Из-за чего это может быть? Выхожу за границы __int64? Подскажите, мальчики, пожалуйста. Вот моя реализация:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
 
int main()
{
   unsigned __int64 a, b, c;
 
   while(scanf("%I64d %I64d %I64d", &a, &b, &c) == 3)
   {
       unsigned __int64 r = 1;
 
       while(b != 0)
       {
           if(b%2 != 0) r = (r * a)%c;
           b /= 2;
           a = (a * a) % c;
       }
 
       printf("%I64d\n", r);
   }
   return 0;
} //main
Для написания этой программы использовала "алгоритм русского крестьянина" а также известный факт о том, что http://www.cyberforum.ru/cgi-bin/latex.cgi?(A * B) mod C = ((A mod C) * (B mod C) ) mod C
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.03.2013, 20:58     Быстрый подсчет A^B mod C или "Алгоритм русского крестьянина"
Посмотрите здесь:
Как использовать символы из русского алфавита, а так же символы типа "█" "░" и т.д.? C++
Алгоритм для реализации оператора "побитовое исключающее ИЛИ" C++
C++ Неправильное отображение русского текста в консоли при использовании setlocale(LC_ALL, "Russian")
"Чудеса типа float" или "Куда девалась информация?" C++
C++ Вывести "Молодой" или "Старый" в зависимости от введенного возраста
Определить, каких букв в тексте больше: "м" или "н" C++
"Точность вычислений" или "Элементарная погрешность" C++
Что применить "\n" или "endl"? C++
"И" ведет себя как "ИЛИ" C++
C++ Подсчет количества "счастливых" билетов с заданной суммой цифр
Массив: Подсчет матрицы 3x3 по средствам класса используя оператор ">>" C++
Подсчет букв "и" во введенной строке C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
HighPredator
5464 / 1830 / 338
Регистрация: 10.12.2010
Сообщений: 5,411
Записей в блоге: 3
12.03.2013, 21:03     Быстрый подсчет A^B mod C или "Алгоритм русского крестьянина" #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int ModExp(unsigned int a,unsigned int b,unsigned int n)
{
    unsigned char bits[64];
    unsigned int d=b;   
    unsigned int k=0;
    while(d>0)
    {
        bits[k]=d%2;
        k++;        
        d/=2;
    }
    d=1;
    for(unsigned int i=k-1;i>-1;i--)
    {
        d=(d*d)%n;
        if(bits[i]==1) d=(d*a)%n;
    }
    return d;
}
roanna
16 / 16 / 2
Регистрация: 11.11.2010
Сообщений: 88
14.03.2013, 16:26  [ТС]     Быстрый подсчет A^B mod C или "Алгоритм русского крестьянина" #3
Спасибо за ответ. Свой код я усовершенствовала, что заменила умножение на стороннюю функцию с испльзованием все того же "алгоритма русского крестьянина". Таким образом я все умножения реализовала через сложения - и времени меньше и осталась в границах __int64!
HighPredator
5464 / 1830 / 338
Регистрация: 10.12.2010
Сообщений: 5,411
Записей в блоге: 3
14.03.2013, 16:30     Быстрый подсчет A^B mod C или "Алгоритм русского крестьянина" #4
roanna, тогда выложите итоговый вариант Мало ли кому-то пригодится
roanna
16 / 16 / 2
Регистрация: 11.11.2010
Сообщений: 88
17.03.2013, 12:32  [ТС]     Быстрый подсчет A^B mod C или "Алгоритм русского крестьянина" #5
Программа использует 1156 KB памяти, среднее время выполнения 0.015 секунды.
Итоговый вариант:
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
 
// ================================================================================
class Ex_1121
{
   unsigned __int64 m_nInputA;
   unsigned __int64 m_nInputB;
   unsigned __int64 m_nInputC;
 
public:
   void ReadInput(); //чтения входящих данных
 
private:
   unsigned __int64 AexpBmodC(unsigned __int64 a, unsigned __int64 b, unsigned __int64 c);
   unsigned __int64 RussianPeasant(unsigned __int64 a, unsigned __int64 b, unsigned __int64 c);
};
 
// --------------------------------------------------------------------------------
// Чтение входящих данных пока не будет введена пустая строка
void Ex_1121::ReadInput()
{
   while(scanf("%I64d %I64d %I64d", &m_nInputA, &m_nInputB, &m_nInputC) == 3)
       printf("%I64d\n", RussianPeasant(m_nInputA, m_nInputB, m_nInputC));
} //Ex_1121
 
// --------------------------------------------------------------------------------
// Алгоритм русского крестьянина для расчета умножения вида:
// (a * a mod c)
unsigned __int64 Ex_1121::AexpBmodC(unsigned __int64 a, unsigned __int64 b, unsigned __int64 c)
{
  unsigned __int64 result = 0;
 
  while(b)
  {
      if(b & 1) result = (result + a) % c;
 
      a = (a + a) % c;
      b >>= 1;
  }
 
  return result;
} //AexpBmodC
 
// --------------------------------------------------------------------------------
// Алгоритм русского крестьянина для решения уравнения вида:
// ((a * a mod c)*...*(a*a mod c)) mod c
// так как известно, что (a*b)mod c = ((a mod c)*(b mod c)) mod c
unsigned __int64 Ex_1121::RussianPeasant(unsigned __int64 a, unsigned __int64 b, unsigned __int64 c)
{
   unsigned __int64 result = 1;
 
   while(b)
   {
       if(b & 1) result = AexpBmodC(result, a, c);
 
       a = AexpBmodC(a, a, c);
       b >>= 1;
   }
 
   return result;
} //RussianPeasant
 
// ================================================================================
int main(int argc, char *argv[])
{ 
   Ex_1121 ex;
  
   ex.ReadInput();
 
   return 0;
} //main
Yandex
Объявления
17.03.2013, 12:32     Быстрый подсчет A^B mod C или "Алгоритм русского крестьянина"
Ответ Создать тему
Опции темы

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