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

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

Answer 2

您正在处理 Modular exponentiation。一种可能的解决方案是避免大数乘法，这会溢出 int，方法是利用以下内容：

Given two integers a and b, the following two equations are equivalent:

c mod m = (a ⋅ b) mod m

c mod m = [(a mod m) ⋅ (b mod m)] mod m

在 Java 中，一个简单的解决方案基于此 section 中解释的算法：

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

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

Calculating 2^n%k using only integers

java

integer

square