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

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

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

C++ Как VC6 заставить понимать long long ?
Написать функцию для перевода переменной типа long в символьную строку в шестнадцатиричном представлении ( ltoah( long num, char s[]) ) и тестирующую C++
C++ Как преобразовать char[8] к unsigned long long?
C++ Подскажите что за типа такой long long int?
Написать функцию, которая принимает два параметра типа unsigned long long и выводит их на экран C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
xecu91
3 / 3 / 0
Регистрация: 09.01.2012
Сообщений: 28
09.01.2012, 15:43     Возведение в степень по модулю для чисел близких к max long long #2
По-моему, имеет место равенство ((A^2)%C) = ((A%C)^2)%С, и это можно использовать
Байт
 Аватар для Байт
13964 / 8795 / 1223
Регистрация: 24.12.2010
Сообщений: 15,933
09.01.2012, 17:06     Возведение в степень по модулю для чисел близких к max long long #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
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16825 / 5246 / 321
Регистрация: 30.03.2009
Сообщений: 14,127
Записей в блоге: 26
09.01.2012, 17:21     Возведение в степень по модулю для чисел близких к max long long #4
Тут скорее математик нужен, чем программист
Байт
 Аватар для Байт
13964 / 8795 / 1223
Регистрация: 24.12.2010
Сообщений: 15,933
09.01.2012, 17:35     Возведение в степень по модулю для чисел близких к max long long #5
Цитата Сообщение от Evg Посмотреть сообщение
Тут скорее математик нужен, чем программист

Не по теме:

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

valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
09.01.2012, 18:02     Возведение в степень по модулю для чисел близких к max long long #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.
prazuber
108 / 108 / 3
Регистрация: 29.04.2010
Сообщений: 240
09.01.2012, 18:08     Возведение в степень по модулю для чисел близких к max long long #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;
}
Код не мой
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
09.01.2012, 18:14     Возведение в степень по модулю для чисел близких к max long long #8
PraZuBeR, не пройдет при значениях x и m близких к 2^63-1, об этом уже автор темы писал в самом начале.
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
09.01.2012, 18:27     Возведение в степень по модулю для чисел близких к max long long #9
можно попробовать решить задачу в лоб:
сделать класс для больших целых чисел негораниченного размера, реализовать для него арифметичечкие операции. ну и по тупому посчитать как для маленьких встроенных типов.
const BigInt x = A * A * A .... * A;
const BigInt result = x - x / C;
Считаться будет долго, но все таки посчитается.
Байт
 Аватар для Байт
13964 / 8795 / 1223
Регистрация: 24.12.2010
Сообщений: 15,933
09.01.2012, 18:49     Возведение в степень по модулю для чисел близких к max long long #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 ...
Только тут приходится из-за больших чисел делать как бы "быстрое" умножение. Складывать-то мы можем, а умножать разрядная сетка не велит...
xecu91
3 / 3 / 0
Регистрация: 09.01.2012
Сообщений: 28
09.01.2012, 19:48     Возведение в степень по модулю для чисел близких к max long long #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
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
09.01.2012, 19:53     Возведение в степень по модулю для чисел близких к max long long #12
Цитата Сообщение от Байт Посмотреть сообщение
Складывать-то мы можем, а умножать разрядная сетка не велит...
я складывать и не предлагаю. Предлагаю все через суммы, просто учитывая, что (A*A) mod C=((A mod C) * (A mod C)) mod C.
Байт
 Аватар для Байт
13964 / 8795 / 1223
Регистрация: 24.12.2010
Сообщений: 15,933
09.01.2012, 21:17     Возведение в степень по модулю для чисел близких к max long long #13
А может быть все-таки обратиться за помощью к старым китайцам?
Вот, нашел 3 хороших взаимно простых числа 2^30 +1, 2^30-1, 2^30-3
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
09.01.2012, 21:33  [ТС]     Возведение в степень по модулю для чисел близких к max long long #14
http://www.e-olimp.com/problems/252
http://www.e-olimp.com/problems/1121

Неужели никто их не решал???
Small Lamer
 Аватар для Small Lamer
142 / 142 / 48
Регистрация: 05.04.2011
Сообщений: 270
09.01.2012, 21:46     Возведение в степень по модулю для чисел близких к max long long #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;
 
}
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
09.01.2012, 21:56  [ТС]     Возведение в степень по модулю для чисел близких к max long long #16
Small Lamer, спасибо большое)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.02.2012, 17:32     Возведение в степень по модулю для чисел близких к max long long
Еще ссылки по теме:

C++ Быстрое вычисление наибольшего общего делителя для unsigned long long int
C++ Не понятный undefined reference to `unsigned long long f<unsigned long long, void>
Тип long long и его ввод\вывод с использованием scanf\printf C++

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

Или воспользуйтесь поиском по форуму:
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
04.02.2012, 17:32     Возведение в степень по модулю для чисел близких к max long long #17
Здесь - двоичное возведение в степень. Реализуется при помощи рекурсии или цикла. При рекурсии 3 варианта (надо a^b):
1) Если b==1, то return a;
2) Если b%2==0, то t=Stepen(a,b/2); return t*t;
3) Иначе return a*Stepen(a,b-1).
Как-то так)
Yandex
Объявления
04.02.2012, 17:32     Возведение в степень по модулю для чисел близких к max long long
Ответ Создать тему
Опции темы

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