Вычислить (a ^ b)% c, где 0 ‹= a, b, c‹ = 10 ^ 18

Как можно посчитать (a ^ b) % c, где 0 <= a, b, c <= 10^18. Здесь (a ^ b) означает a в степени b, а не a xor b.

Мой текущий код проблемы:

unsigned long long bigMod(unsigned long long b,
                          unsigned long long p,
                          unsigned long long m){
    if(b == 1) return b;
    if(p == 0) return 1;
    if(p == 1) return b;

    if(p % 2 == 0){  
        unsigned long long temp = bigMod(b, p / 2ll, m);
        return ((temp) * (temp) )% m;
    }else return (b  *  bigMod(b, p-1, m)) % m;
}

Для этого ввода:

a = 12345 b = 123456789 and c = 123456789012345

ожидаемый результат должен быть:

59212459031520

c++ math modular-arithmetic
person Abu Hanifa    schedule 09.09.2015    source источник
comment
Возведение в степень возведением в квадрат может быть полезной отправной точкой. Если вы заметили (a**b)%c == ((a%c)**b)%c), добавить модуль к формуле не так уж и сложно.   -  person Kevin    schedule 09.09.2015
comment
Возможная копия вычисления a ^ b mod c.   -  person Andrew Morton    schedule 09.09.2015
comment
Я пытался ((a% m) * (b% m))% m, но, возможно, мой подход неверен.   -  person Abu Hanifa    schedule 09.09.2015
comment
@AndrewMorton может быть, я пробовал, что подход не подходит для этого лимита   -  person Abu Hanifa    schedule 09.09.2015
comment
возможный дубликат Расчет мощности (a, b) mod n   -  person phuclv    schedule 09.09.2015
comment
Расчет (a ^ b)% MOD. Для 64-битных a и b используйте __int128 для промежуточного умножения. Если его нет, напишите собственное 128-битное умножение. Ссылка: Самый быстрый способ вычислить 128-битное целое число по модулю 64-битного целого, Самый точный способ выполнить комбинированную операцию умножения и деления в 64-разрядной версии?   -  person phuclv    schedule 09.09.2015
comment
@AbuHanifa Подход ((a% m) ^ (b% m)% m терпит неудачу, потому что показатель степени должен быть модулирован на phi (m), где phi - это функция Эйлера. Если m простое, то phi (m) = m-1, и вы можете уменьшить как ((a% m) ^ (b% (m-1)))% m.   -  person Nico Schertler    schedule 09.09.2015
comment
@NicoSchertler спасибо за советы. очень полезно   -  person Abu Hanifa    schedule 09.09.2015
comment
0 ‹= a, b, c‹ = 10 ^ 18 конечно тоже нужно c > 0.   -  person chux - Reinstate Monica    schedule 20.09.2017

Ответы (2)


arrow_upward
2
arrow_downward

У вас проблема с temp * temp (долгое долгое переполнение). Вы можете опустить эту проблему, используя алгоритм быстрой модульной мощности, чтобы умножить их на mod m. Вот у вас рабочий код:

unsigned long long bigMultiply(unsigned long long b,unsigned long long p, unsigned long long m)
{
  if(p == 0 )return b;
  if(p%2 == 0)
  {  
     unsigned long long temp = bigMultiply(b,p/2ll,m);
     return ((temp)+(temp))%m;
  }
  else
    return (b  +  bigMultiply(b,p-1,m))%m;
}    
unsigned long long bigMod(unsigned long long b,unsigned long long p, unsigned long long m)
{

  if(b == 1)
    return b;
  if(p == 0 )return 1;
  if( p == 1)return b;
  if(p%2 == 0)
  {  
     unsigned ll temp = bigMod(b,p/2ll,m);
     return bigMultiply(temp,temp,m);
  }
  else
    return (b  *  bigMod(b,p-1,m))%m;
}
person Kamil    schedule 09.09.2015
comment
Проблемы с некоторыми угловыми случаями: bigMod(1, p, 1) равно 1 и должно быть 0. Предложите if(b == 1) return b%m; Аналогичное для if(p == 0 )return 1; - ›if(p == 0 )return 1%m; для обработки m==1 и if( p == 1)return b; -› if( p == 1)return b%m; для обработки b >= m. - person chux - Reinstate Monica; 20.09.2017
comment
Я совершенно уверен, что b * bigMod(b,p-1,m) может легко переполниться. Кроме того, этот код очень приятный, но имеет некоторые ограничения: (temp)+(temp) все еще может переполняться, когда m > ULLONG_MAX/2, но это выходит за рамки c <= 10^18 OP. - person chux - Reinstate Monica; 20.09.2017

arrow_upward
0
arrow_downward

Я использую этот код на c ++:

long long power(long long a, long long b, long long c)
{
    if (b==0)
    {
        return 1;
    }

    if (b % 2 == 0)
    {
        long long w = power(a, b/2, c);
        return (w*w) % c;
    }
    else
    {
        int w = power(a, b-1, c);
        return (a*w) % c;
    }
}

Имеет логарифмическую сложность.

person Kamil    schedule 09.09.2015
comment
он не работает, если a и b оба 64-битные, поскольку w*w требуется 128-битный тип для хранения - person phuclv; 09.09.2015