我需要編寫一個(gè)代碼來獲取 2 個(gè)變量 (n,k) 并打印 (2^n)%k 的答案。我只能使用整數(shù)，不能使用方法，不能使用數(shù)組，不能使用數(shù)學(xué)。等等。到目前為止我有這個(gè)：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貢獻(xiàn)1850條經(jīng)驗(yàn) 獲得超11個(gè)贊
您正在處理模冪。int一種可能的解決方案是通過利用以下優(yōu)勢(shì)來避免大數(shù)相乘，這會(huì)溢出：
給定兩個(gè)整數(shù) a 和 b，以下兩個(gè)方程是等價(jià)的：
c mod m = (a ? b) mod m
c mod m = [(a mod m) ? (b mod m)] mod m
在 Java 中，基于本節(jié)中解釋的算法的簡單解決方案：
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;
}
ABOUTYOU
TA貢獻(xiàn)1812條經(jīng)驗(yàn) 獲得超5個(gè)贊
如果您的問題是它無法存儲(chǔ)超過 2^31，那是因?yàn)槟枰褂瞄L數(shù)據(jù)類型來存儲(chǔ)該值。long 可以存儲(chǔ)最大值 2^63（有符號(hào)）。
添加回答
舉報(bào)
0/150
提交
取消