16 / 16 / 3
Регистрация: 11.11.2010
Сообщений: 88
1

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

12.03.2013, 20:58. Показов 2763. Ответов 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
Для написания этой программы использовала "алгоритм русского крестьянина" а также известный факт о том, что https://www.cyberforum.ru/cgi-bin/latex.cgi?(A * B) mod C = ((A mod C) * (B mod C) ) mod C
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.03.2013, 20:58
Ответы с готовыми решениями:

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно"
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;,...

Вставить пробел после каждого символа "." "," "!" или "?", если за этими символами не следует пробел
Вставить пробел после каждого символа &quot;.&quot; &quot;,&quot; &quot;!&quot; или &quot;?&quot;, если за этими символами не следует...

Как использовать символы из русского алфавита, а так же символы типа "█" "░" и т.д.?
Как использовать символы из русского алфавита, а так же символы типа &quot;█&quot; &quot;░&quot; и т.д.?

Написать программу, которая запрашивает у пользователя номер дня недели и выводит одно из сообщений: "Рабочий день","Суббота" или "Воскресенье"
Написать программу, которая запрашивает у пользователя номер дня недели и выводит одно из...

4
6042 / 2157 / 753
Регистрация: 10.12.2010
Сообщений: 6,007
Записей в блоге: 3
12.03.2013, 21:03 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;
}
1
16 / 16 / 3
Регистрация: 11.11.2010
Сообщений: 88
14.03.2013, 16:26  [ТС] 3
Спасибо за ответ. Свой код я усовершенствовала, что заменила умножение на стороннюю функцию с испльзованием все того же "алгоритма русского крестьянина". Таким образом я все умножения реализовала через сложения - и времени меньше и осталась в границах __int64!
0
6042 / 2157 / 753
Регистрация: 10.12.2010
Сообщений: 6,007
Записей в блоге: 3
14.03.2013, 16:30 4
roanna, тогда выложите итоговый вариант Мало ли кому-то пригодится
0
16 / 16 / 3
Регистрация: 11.11.2010
Сообщений: 88
17.03.2013, 12:32  [ТС] 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
2
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.03.2013, 12:32
Помогаю со студенческими работами здесь

Дан текст, хранящийся в текстовом файле f, каждый символ которого может быть малой буквой, цифрой или одним из знаков "+", "-", "*".
Дан текст, хранящийся в текстовом файле f, каждый символ которого может быть малой буквой, цифрой...

Определить, какая из точек "В" или "С" расположены ближе к точке "А".
На оси Ох расположены 3 точки А, В и С. Определить, какая из точек &quot;В&quot; или &quot;С&quot; расположены ближе к...

Алгоритм для реализации оператора "побитовое исключающее ИЛИ"
Помогите пожалуйста не могу делать. Для заданных двух целых чисел предложите описание алгоритма...

""D:\"" не является внутренней или внешней командой, исполняемой программой или пакетным файлом
Только начал изучать С++, и уже в самом начале напоролся на ошибку. Перерыл весь гугл, ответа не...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru