没有使用大整数的大幂

我有一个问题，我不得不计算一个数组的大幂数的和，并返回结果。例如arr = [10,12,34,56]，那么输出应该是 10^1 + 12^2 + 34^3 + 56^4。这里的输出可能非常大，所以我们被要求在输出中取一个10^10 + 11的模，然后返回它。蟒蛇，但在Java最初我使用BigInteger，并得到了一半的测试用例，所以我想用龙，然后用模块指数计算功耗，但然后我得到了错误的输出是精确的所有负面，因为它显然超出了极限。没有使用大整数的大幂

这是我的代码使用长和模块指数。

static long power(long x, long y, long p) 
{ 
    long res = 1;  // Initialize result 

    x = x % p; // Update x if it is more than or 
       // equal to p 

    while (y > 0) 
    { 
     // If y is odd, multiply x with result 
     if ((y & 1)==1) 
      res = (res*x) % p; 

     // y must be even now 
     y = y>>1; // y = y/2 
     x = (x*x) % p; 
    } 
    return res; 
} 

static long solve(int[] a) { 
    // Write your code here 
    Long[] arr = new Long[a.length]; 

    for (int i = 0; i < a.length; i++) { 
     arr[i] = setBits(new Long(a[i])); 
    } 
    Long Mod = new Long("10000000011"); 
    Long c = new Long(0); 
    for (int i = 0; i < arr.length; i++) { 
     c += power(arr[i], new Long(i + 1),Mod) % Mod; 
    } 

    return c % Mod; 
} 

static long setBits(Long a) { 
    Long count = new Long(0); 
    while (a > 0) { 
     a &= (a - 1); 
     count++; 
    } 
    return count; 
}

然后我也尝试二进制幂，但没有工作了me.How做我做到这一点，而无需使用大的整数，那样容易，因为我在Python

来源

2017-07-16 ani

BigInteger究竟是如何失败的？因为使用这个库是最容易编码的解决方案吗？ – GhostCat

@GhostCat我得到了一半的测试用例 – ani

你正在重复你已经说过的。 Tle是什么意思？但想一想：你是对的 - 你应该专注于获得模数解决方案。用较小的数字进行计算总是更高效。 – GhostCat

您已经添加了一个额外的零价值得到了它mod，应该是100000011. 希望这能解决它

来源

2017-07-16 05:39:56 neilharia7

不，它没有...我仍然得到错误的答案 – ani

分享链接到问题 – neilharia7

没有使用大整数的大幂

回答

相关问题