计算(a ^ b)％c，其中0 <= a，b，c <= 10 ^ 18 [英] Calculate (a^b)%c where 0&lt;=a,b,c&lt;=10^18

问题描述

如何计算(a ^ b) % c，其中0 <= a, b, c <= 10^18. 在这里，(a ^ b)表示a等于电源b，而不是a xor b.

How can I calculate (a ^ b) % c, where 0 <= a, b, c <= 10^18. Here, (a ^ b) means a to the power b, not a xor b.

我当前针对该问题的代码是:

My current code for the problem is:

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

推荐答案

您遇到temp * temp(长时间溢出)问题.您可以使用快速mod功率的算法将它们乘以mod m来忽略此问题.这里您有工作代码:

You have a problem with temp*temp (long long overflow). You can omit this problem using algorithm of fast mod power to multiply them mod m. Here You have working code:

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;
}

这篇关于计算(a ^ b)％c，其中0 <= a，b，c <= 10 ^ 18的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！