2的121次方 除以 2047 的餘數等於多少

Question

2的121次方 除以 2047 的餘數等於多少

請問有大大知道嗎@@

Answer 1

211= 2048，除2047 餘 1
212= 4096，除2047 餘 2
213= 8192，除2047 餘 4
214=16384，除2047 餘 8
215=32768，除2047 餘 16
216=65536，除2047 餘 32
222=2097152除2047 餘1
222=211+11，除2047 餘211就是餘1
2121=211+110，除2047餘 2110
2110=299+11，除2047餘 211，餘1


2007-01-25 22:12:42 補充：
原理：
A / B = Q R/B　　9 / 4 = 2 1/4
2A / B = 2Q 2R/B　18 / 4 = 4 2/4

令 q = 2^11 / 2047 的商
　r = 2^11 / 2047 的餘數
2^12 / B = 2*2^11 / B = 2q 2r/B
2^(11 x) / B = 2^x * 2^11 / B = 2^x * q 2^x * r / B

2007-01-25 22:14:02 補充：
＋　又都不見了

2007-01-25 22:22:05 補充：
上列少＋的是
... Q＋R/B　　2 ＋ 1/4
... 2Q＋R/B　　4＋2/4
... 2q＋2r/B
2^(11＋x) ... q ＋ 2^x * r/B

2^x * r/B 大於B，不能算是除B的餘數。
所以，要再拿它來除B，其餘數才是餘數。

而 2^x 除 B 的餘數的規則已經找到，r又小於B。
所以，2^11 除 2047 的餘數是 r * 2^(x除11的餘數 ＋ 11)
而 x = 110，110除11是餘11，所以是r * 2^11/2047 的餘數
而 r =1，所以，是 1 * 2^11/2047的餘 = 1 * 1 = 1

Answer 2

既然這是程式設計版，我就用程式設計的方式回答你

num = 1;
for (i = 1; i <= 121; i++)
{
num *= 2;
num %= 2047;
}

答案是1

2007-01-28 12:13:16 補充：
每一回合都 mod 2047就可以了
原理是這樣:
(2 * 2 * 2 * 2 ..... * 2)
= (((2 * 2) mod 2047) * 2) mod 2047) ...
假設2 * 2 * 2 * ... 中途算出來有個數字是2048
那麼 (2048 * 2 * 2 .... * 2) = ((2047 1) * 2 * 2 ... * 2)
前面那項 2047 不管後面怎麼乘，都會被2047整除
也就是說只要留下後面的餘數 1 就可以了
大概是這樣的概念 :-)

2007-01-28 12:44:22 補充：
補充說明，perl不是萬能
現在問的是(2^121) mod 2047
要是問的是(2^1000000000) mod 2047呢?
有興趣的可以去跑跑看perl需要跑多久
但是基本上C語言用暴力for迴圈一樣也需要一些時間

2007-01-28 12:45:23 補充：
提供一個更快的方法，可以瞬殺
#include
int power(int a, int p)
{
int t;
if (!p) return (1);
if (p & 1) return (a * power(a, p-1)) % 2047;
t = power(a, p >> 1);
return (t * t) % 2047;
}
int main()
{
printf("%d\\n", power(2, 1000000000));
}
答案是1024

2007-01-28 12:45:31 補充：
假設現在要算(2^p) mod 2047
想法是把p換成二進位表示
要是二進位表示的最後一位是1的話，就去算2^(p-1) mod 2047
然後再乘以2
要是二進位表示的最後一位是0
那我們就可以算2^(p/2) mod 2047，將兩個2^(p/2) mod 2047乘在一起就是答案
大約只要花log2(p) = log2(1000000000) = 30左右的運算時間就可以算完

Answer 3

兩位大大的答案正確
但是方法稍為麻煩了些
2121 (mod 2047)
= (211)11 (mod 2047)
= (2048)11 (mod 2047)
= (1)11 (mod 2047)
= 1 (mod 2047)
= 1

如果題目改成 2122 (mod 2047)
=> 2122 (mod 2047)
= 211*11+1 (mod 2047)
= (211)11*2 (mod 2047)
= (2048)11*2 (mod 2047)
= (1)11*2 (mod 2047)
= 1*2 (mod 2047)
= 2
如果有問題, 請來函討論. 不然, 我可能會錯失你再補充的疑點.

Answer 4

大家都用數學來解，我用程式語言的來解看看！

用 perl ，一行就得到答案了。

C:\\>perl -e "use bignum; print 2 ** 121 % 2047"
1

Answer 5

2的121次方
=2.65846*10^36次方

除上2047
=1.29871*10^33次方

後面是10的幾次方