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

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

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

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

12.03.2013, 20:58. Просмотров 1405. Ответов 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++
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;, &quot;жарко&quot;, &quot;холодно&quot;, &quot;очень холодно&quot;. Я так...

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
HighPredator
5477 / 1843 / 343
Регистрация: 10.12.2010
Сообщений: 5,435
Записей в блоге: 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;
}
roanna
16 / 16 / 2
Регистрация: 11.11.2010
Сообщений: 88
14.03.2013, 16:26  [ТС] #3
Спасибо за ответ. Свой код я усовершенствовала, что заменила умножение на стороннюю функцию с испльзованием все того же "алгоритма русского крестьянина". Таким образом я все умножения реализовала через сложения - и времени меньше и осталась в границах __int64!
HighPredator
5477 / 1843 / 343
Регистрация: 10.12.2010
Сообщений: 5,435
Записей в блоге: 3
14.03.2013, 16:30 #4
roanna, тогда выложите итоговый вариант Мало ли кому-то пригодится
roanna
16 / 16 / 2
Регистрация: 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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.03.2013, 12:32
Привет! Вот еще темы с ответами:

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

Обчисление введенной строки любого формата(пример:"(2+3)/4*2"или"2+3"или ...) - C++
Доброе время суток ! Если у когото есть такое код выложыте пожалуста,буду примного благодарен, или подскажыте какойто алгоритм или где...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Реализовать условие "больше или равно", "меньше или равно" для простых дробей в классе - C++
как реализовать условие больше или равно, меньше или равно для простых дробей в классе?


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

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

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