仅使用整数计算 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 m

c 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（有符号）。