С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

Возведение в степень по модулю для чисел близких к max long long - C++

09.01.2012, 14:20. Просмотров 5881. Ответов 16
Метки нет (Все метки)

Даны числа A,B,C<=2^63-1 Надо посчитать A^B mod С.
прошу не выкладывать стандартный алгоритм для Int, так как неверный ответ в итоге получается.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.01.2012, 14:20
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Возведение в степень по модулю для чисел близких к max long long (C++):

Не понятный undefined reference to `unsigned long long f<unsigned long long, void> - C++
test.cpp: #include &lt;iostream&gt; template &lt;typename FormalType, typename FactType = typename std::enable_if&lt;std::is_same&lt;FormalType,...

Несмотря на то, что переменная С имеет тип long int, возведение, к примеру, 100 в степень 5 совершается неверн - C++
Ребят, раньше программировал ( на уровне любителя ) только на скриптовых языках с динамической типизацией (в основном JS и Python), но так...

Быстрое вычисление наибольшего общего делителя для unsigned long long int - C++
Даны два числа типа unsigned long long int, в них могут оказаться любые представимые значения, требуется максимально быстро вычислить...

Сложение чисел типа long long - C++
Пыталась сложить 2 больших числа (в пределах long long), не получилось. В чем дело? #include &lt;cmath&gt; #include &lt;cstdio&gt; #include...

Написать функцию для перевода переменной типа long в символьную строку в шестнадцатиричном представлении ( ltoah( long num, char s[]) ) и тестирующую - C++
Написать функцию для перевода переменной типа long в символьную строку в шестнадцатиричном представлении ( ltoah( long num, char s) ) и...

Как char[] перевести в битовую маску long long(64 бита) и наоборот? - C++
Как char перевести в битовую маску long long(64 бита) и наоборот?

16
xecu91
3 / 3 / 0
Регистрация: 09.01.2012
Сообщений: 28
09.01.2012, 15:43 #2
По-моему, имеет место равенство ((A^2)%C) = ((A%C)^2)%С, и это можно использовать
0
Байт
Нарушитель
Эксперт C
16684 / 10946 / 1682
Регистрация: 24.12.2010
Сообщений: 21,341
09.01.2012, 17:06 #3
Цитата Сообщение от xecu91 Посмотреть сообщение
По-моему, имеет место равенство ((A^2)%C) = ((A%C)^2)%С, и это можно использовать
Идея хорошая, но при C близком к 2^64 и A<C (A%C)^2 все равно вылезет за сетку.
Может быть здесь применить китайскую теорему об остатках?
Т.е. найти 3 взаимно-простых числа < 2^32, но произведение которых > 2^64, и делать действия по их модулю, а потом результат восстановить.
Пару таких чисел могу подсказать: 2^32-1, 2^32-3
0
Evg
Эксперт CАвтор FAQ
18377 / 6424 / 441
Регистрация: 30.03.2009
Сообщений: 17,833
Записей в блоге: 28
09.01.2012, 17:21 #4
Тут скорее математик нужен, чем программист
0
Байт
Нарушитель
Эксперт C
16684 / 10946 / 1682
Регистрация: 24.12.2010
Сообщений: 21,341
09.01.2012, 17:35 #5
Цитата Сообщение от Evg Посмотреть сообщение
Тут скорее математик нужен, чем программист

Не по теме:

А еще лучше в одном лице. Но где ж его найдешь, такого универсала. Времена Леонардо давно прошли

0
valeriikozlov
Эксперт С++
4675 / 2501 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
09.01.2012, 18:02 #6
В голову пришла одна идея, может быть не очень быстро, но точно должно считать.
Сначало нужно вычислить A^2 mod C
Вычисляем так:
A+A , если результат получился отрицательный, то всегда можно вычислить положительный результат (A+A) mod C
Итак имеем (A*2) mod C
Теперь можем вычислить (A*4) mod C
Складываем (A+A) mod C и (A+A) mod C, опять если результат отрицательный, то можем вычмслить положительный (A*4) mod C
И т.д.
Кстати промежуточные результаты можно запоминать, они еще пригодятся, если A не степень 2.
Таким образом вычислим (A^2) mod C
Имея (A^2) mod C , будем сразу вычислять (A^4) mod C, затем (A^8) mod C и т.д. Эти промежуточные результаты теперь тоже лучше запоминать, они нам тоже пригодятся, если B не степень 2.
1
prazuber
110 / 110 / 3
Регистрация: 29.04.2010
Сообщений: 240
09.01.2012, 18:08 #7
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
/* compute x^y mod m.
   assume m >= 2.
   overflow is impossible. */
int modpow(int x, int y, int m) {
  long acc = 1, z = x % m;
  while (y) {
    if (y & 1)
      acc = (acc * z) % m;
    z = (z * z) % m;
    y >>= 1;
  }
  return acc;
}
Код не мой
0
valeriikozlov
Эксперт С++
4675 / 2501 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
09.01.2012, 18:14 #8
PraZuBeR, не пройдет при значениях x и m близких к 2^63-1, об этом уже автор темы писал в самом начале.
0
DU
1484 / 1130 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
09.01.2012, 18:27 #9
можно попробовать решить задачу в лоб:
сделать класс для больших целых чисел негораниченного размера, реализовать для него арифметичечкие операции. ну и по тупому посчитать как для маленьких встроенных типов.
const BigInt x = A * A * A .... * A;
const BigInt result = x - x / C;
Считаться будет долго, но все таки посчитается.
0
Байт
Нарушитель
Эксперт C
16684 / 10946 / 1682
Регистрация: 24.12.2010
Сообщений: 21,341
09.01.2012, 18:49 #10
Цитата Сообщение от valeriikozlov Посмотреть сообщение
В голову пришла одна идея, может быть не очень быстро, но точно должно считать.
Сначало нужно вычислить A^2 mod C
Вычисляем так:
A+A , если результат получился отрицательный, то всегда можно вычислить положительный результат (A+A) mod C
Итак имеем (A*2) mod C
Теперь можем вычислить (A*4) mod C
Складываем (A+A) mod C и (A+A) mod C, опять если результат отрицательный, то можем вычмслить положительный (A*4) mod C
И т.д.
Кстати промежуточные результаты можно запоминать, они еще пригодятся, если A не степень 2.
Таким образом вычислим (A^2) mod C
Имея (A^2) mod C , будем сразу вычислять (A^4) mod C, затем (A^8) mod C и т.д. Эти промежуточные результаты теперь тоже лучше запоминать, они нам тоже пригодятся, если B не степень 2.
Есть такой алгоритм быстрого возведения в степень (целую) Там тоже считается x^2 x^4 ...
Только тут приходится из-за больших чисел делать как бы "быстрое" умножение. Складывать-то мы можем, а умножать разрядная сетка не велит...
1
xecu91
3 / 3 / 0
Регистрация: 09.01.2012
Сообщений: 28
09.01.2012, 19:48 #11
Цитата Сообщение от xecu91 Посмотреть сообщение
По-моему, имеет место равенство ((A^2)%C) = ((A%C)^2)%С, и это можно использовать
возвращаясь к этому, по-моему можно немножко модифицировать так, чтобы (A%C)^2 не вылезло за сетку.
делаем res += A%C, пока res < 2^64, как только res >= 2^64 щёлкаем счетчиком, продолжаем до тех пор, пока не "наплюсуем" (A%C)^2 и пользуемся тем, что (X+Y)%Z = (X%Z + Y%Z)%Z
0
valeriikozlov
Эксперт С++
4675 / 2501 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
09.01.2012, 19:53 #12
Цитата Сообщение от Байт Посмотреть сообщение
Складывать-то мы можем, а умножать разрядная сетка не велит...
я складывать и не предлагаю. Предлагаю все через суммы, просто учитывая, что (A*A) mod C=((A mod C) * (A mod C)) mod C.
0
Байт
Нарушитель
Эксперт C
16684 / 10946 / 1682
Регистрация: 24.12.2010
Сообщений: 21,341
09.01.2012, 21:17 #13
А может быть все-таки обратиться за помощью к старым китайцам?
Вот, нашел 3 хороших взаимно простых числа 2^30 +1, 2^30-1, 2^30-3
0
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
09.01.2012, 21:33  [ТС] #14
http://www.e-olimp.com/problems/252
http://www.e-olimp.com/problems/1121

Неужели никто их не решал???
0
Small Lamer
142 / 142 / 48
Регистрация: 05.04.2011
Сообщений: 270
09.01.2012, 21:46 #15
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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
 
using namespace std;
 
typedef long long LL;
 
#define SPR(x) ((x)*(x))
#define len(t) ((int)t.length())
#define base 10;
#define fname ""
#define sz (1000 * 1000)
#define sz2 1000
#define EPS (1e-8)
#define INF ((int)1e9 + 9)
//const double PI  = acos(-1.0);
 
LL a , b , c , ans;
 
LL mult(LL a , LL b)
{
    LL res = 0;
    while (b > 0)
    {
        if (b % 2 == 1)
        {
            b--;
            res = (res + a) % c;
            
        }
        a = (a + a) % c;
        b /= 2;
    
    }
    return res;
    
}
 
int main(){
    //freopen(fname".in", "r", stdin);
    //freopen(fname".out", "w", stdout);
 
    cin >> a >> b >> c;
    ans = 1;
    while (b > 0)
    {
        if (b % 2 == 1)
        {
            b--;
            ans = mult(ans , a);
        
        }
        b /= 2;
        a = mult(a , a);
    
    }
    cout << ans;
 
    return 0;
 
}
1
09.01.2012, 21:46
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.01.2012, 21:46
Привет! Вот еще темы с ответами:

Нюансы синтаксиса: что означает запись typedef long long i64 ? - C++
Что означает эта строчка? typedef long long i64; Как я понял, функция typedef позволяет добавить имя типу данных. Но зачем long...

Тип long long и его ввод\вывод с использованием scanf\printf - C++
Добрый день! Мне в программе надо вывести и ввести, соответственно, некоторые данные с помощью scanf и printf. По сути у меня выглядит...

Работа с unsigned long long int на 32-битных системах - C++
В программе испольуется тип данных unsigned long int, но в некоторых (хотя и очень редких) случаях этого диапазона может быть недостаточно....

Как преобразовать const char * в long в С++, 0xE0E040BF в long - C++
Помогите пожалуйста преобразовать текст в число на C++ const char * value=cmd; long ircode = atol(value); ...


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

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

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