仅使用整数计算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(带符号(。