仅使用整数计算 2^n%k

Question

我需要编写一个代码来获取 2 个变量 (n,k) 并打印 (2^n)%k 的答案。

我只能使用整数，不能使用方法，不能使用数组，不能使用数学。等等。到目前为止我有这个：

int n = myScanner.nextInt();  

    int k = myScanner.nextInt();   

    int num = 1;

    int modulo = 1;

    for (int i = 0; i < n; i++) {    

            num = num * 2;  

            modulo *= 2%k;

    }

    modulo = modulo%k;

    System.out.println(modulo);

问题是 int 本身的范围，不超过 2^31...但我仍然需要让它以某种方式工作，任何帮助将非常感激！

Answer 1

您正在处理模幂。int一种可能的解决方案是通过利用以下优势来避免大数相乘，这会溢出：给定两个整数 a 和 b，以下两个方程是等价的：c mod m = (a ⋅ b) mod mc mod m = [(a mod m) ⋅ (b mod m)] mod m在 Java 中，基于本节中解释的算法的简单解决方案：int mod(int base, int exponent, int modulus) {  if (modulus == 1) return 0;  int c = 1;  for (int i = 0; i < exponent; i++) {    c = (c * base) % modulus;  }  return c;}

Answer 2

如果您的问题是它无法存储超过 2^31，那是因为您需要使用长数据类型来存储该值。long 可以存储最大值 2^63（有符号）。