我需要編寫一個代碼來獲取 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...但我仍然需要讓它以某種方式工作，任何幫助將非常感激！
2 回答
慕蓋茨4494581
TA貢獻1850條經驗 獲得超11個贊
您正在處理模冪。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;
}
添加回答
舉報
0/150
提交
取消