java - 设置位与指数模算术结合

我昨天在一个挑战中遇到了这个问题。我以为自己编码正确，示例测试用例通过了。但是，甚至没有一个测试用例在后端通过。这是我的代码。拜托，有人，帮帮我。挑战对我来说已经结束，所以我不能再提交了。但是我想从错误中学习。谢谢。

  import java.io.*;
//import java.util.*;


public class TestClass {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wr = new PrintWriter(System.out);
         int n = Integer.parseInt(br.readLine().trim());
         String[] arr_a = br.readLine().split(" ");
         int[] a = new int[n];
         for(int i_a=0; i_a<arr_a.length; i_a++)
         {
            a[i_a] = Integer.parseInt(arr_a[i_a]);
         }

         long out_ = solve(a);
         System.out.println(out_);

         wr.close();
         br.close();
    }
    static long solve(int[] a){
        // Write your code here
        long sum = 0l;
        long MAX = 10000000011l;
        long i = 1l;
        for(int x : a) {
            long count = 0;
            while(x>0) {
                x &= (x-1l);
                count++;
            }
            long res = 1l;
            long temp = i;
            count = count % MAX;
            while(temp > 0) {
                if((temp & 1l) == 1l) {
                    res = (res * count) % MAX;
                }
                temp = temp >> 1l;
                count = ((count % MAX) * (count % MAX)) % MAX;

            }

            long t =((sum%MAX) + (res % MAX))%MAX;
            sum = t;
            i++;
        }

        return sum;
    }
}

最佳答案

“甚至没有通过一个测试用例”有点奇怪，但是我看到的唯一错误是您的exponentiation by squaring部分。

您的所有数字都小于10^10 + 11，但是此常数超过32位，并且在乘时会出现溢出(因为long是64位有符号整数)。

这可以通过几种方法解决:

(a*b) % M操作可以使用类似于“通过平方求幂”实现的算法来完成。您只需要用加法替换所有乘法即可。结果，乘法被O(log(n))加法和“乘以2”运算所代替。示例实施:

static long multiply(long a, long b, long M) {
    long res = 0;
    long d = a % M;

    while (b > 0) {
        if ((b & 1) == 1) {
            res = (res + d) % M;
        }

        b >>= 1;
        d = (d + d) % M;
    }
    return res;
}

您可以只为先前计算的步骤缓存b^i % M号。对于设置位的每个数量(没有那么多设置位)，您可以保存以前计算的值和last(b)-i具有a[i]设置位时的最后一个b。然后，使用从last(b) + 1到当前索引i的线性循环来计算新值。

使用BigInteger进行乘法。

关于java - 设置位与指数模算术结合，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45115797/