大整數(shù)求余數(shù)的問題分析問題描述最近在學(xué)習(xí)一些資料的時候正好看到一些和大整數(shù)求余數(shù)相關(guān)的問題，這些問題粗粗看來似乎有點麻煩。但是當(dāng)結(jié)合一些有關(guān)數(shù)學(xué)的特性來分析時，會覺得很有意思。問題1:求一個整數(shù)X的N次方除以某個整數(shù)P的余數(shù)。用數(shù)學(xué)公式表示則如下：X^modP)其中N>=0,P>0.這個問題需要考慮的就是如果N比較大的時候，很可能就超出我們所用一般數(shù)據(jù)類型所能表示的范圍。如果直接去求X的N次方，就算有數(shù)據(jù)能保存的下來，肯定也會消耗大量的時間和空間。問題2:給定一個很大的數(shù)，求它除以某個整數(shù)P的余數(shù)。這個數(shù)因為足夠大到?jīng)]辦法用普通的數(shù)據(jù)類型來表示，所以需要用一個整數(shù)類型的數(shù)組或字符串來保存。結(jié)果也是要求XmodP問題1分析最初分析我們先來看第一個問題。這個問題假定X和P并不是太大，可以用一個計算機的常用數(shù)據(jù)類型來表示。一種最簡單直白的方法就是我們直接將所有N個X相乘，然后再對被除數(shù)P相除，求余數(shù)。當(dāng)然，這是基于一個前提，我們有能夠保存足夠大的數(shù)據(jù)類型。如果我們對這種思路的時間和空間復(fù)雜度做一個粗略的估計的話，會發(fā)現(xiàn)，假設(shè)X是int類型的整數(shù)，占4個字節(jié)，而最壞的情況就是每次相乘的結(jié)果就占用的結(jié)果增加4個字節(jié)，這樣N次乘積就需要占用4N字節(jié)的空間。而如果算上每次相乘的中間結(jié)果，占用的空間就達到N*N的量級。再看時間復(fù)雜度，假定兩個int類型的整數(shù)乘積的運算時間單位為1的話，在沒有任何優(yōu)化假定的前提下，一個32位整數(shù)和64位整數(shù)乘積的時間則為原來的兩倍。如果以這個標(biāo)準(zhǔn)來分析的話，后面的時間復(fù)雜度也到了N*N量級。第一步改進可見，雖然前面這種辦法雖然理論上可行，但是實際上時間和空間復(fù)雜度太大，不太合適。現(xiàn)在我們再來看看另外一種思路。因為問題的關(guān)鍵就是指數(shù)N比較大，如果能將指數(shù)能夠降下來，將其轉(zhuǎn)換成對等的表達式，則問題就好解決了。我們看前面求乘積的過程，假定是最簡單的情況，N=2，則相當(dāng)于求(X*X)modD如果利用整數(shù)求余數(shù)的性質(zhì)，我們發(fā)現(xiàn)他們滿足下面的性質(zhì)：(XT)[X(YmodP)]modF=[(XmodP)?(YmodP)]modF這個等式的證明可以參照相關(guān)的數(shù)學(xué)材料或者文章后面的補充證明部分。通過這個性質(zhì)，至少我們可以發(fā)現(xiàn)，對于兩個數(shù)的乘積求余數(shù)，我們可以先求一個數(shù)的余數(shù)，然后再將這個余數(shù)乘以另外一個數(shù)再求余數(shù)。這樣就可以求出來兩個數(shù)乘積的余數(shù)。那么，如果對于3個，4個甚至更多的數(shù)的乘積求余數(shù)呢？我們可以將這個等式擴展一下，對于3個數(shù)的乘積，我們可以先求出前面兩個數(shù)乘積的余數(shù)，再和第三個數(shù)相乘求。依次類推，重復(fù)N次就可以求出N次方的結(jié)果。于是，基于這種思路，我們可以寫出如下的代碼：Java代碼-iz_1-publicstaticlongpower(longx,longn,longp){if(n==0)return1;5.longtmp=x%p;for(longi=0;i<n-1;i++)TOC\o"1-5"\h\z{tmp=(x*tmp)%p;\o"CurrentDocument"}returntmp;}這種方法和前面的思路比起來，有一個進步的地方，就是每次運算的時候都對中間結(jié)果求模運算，使得結(jié)果都在普通數(shù)據(jù)類型可以保存的范圍內(nèi)，這樣不會需要額外的存儲空間。而時間的復(fù)雜度主要取決于運算的指數(shù)，所以時間復(fù)雜度為o(N)。這樣我們就找到了一個還不錯的解決方法了。再進一步考慮前面的辦法雖然是已經(jīng)在一個o(N)的范圍了，可是如果N很大的話，我們還是要做一個很大的循環(huán)運算。還有沒有可能使得我們的方法更加有效率呢？我們求X的N次方，可以根據(jù)N的性質(zhì)做如下的分析：當(dāng)N為偶數(shù)的情況下：=必」那么，就有如下的等式成立：X'modP=(XX)廖仞modP[(X?X)modP]LW幻modP后面這一部分的等式成立是基于模運算的這么一個特性：X、modF土(XmodP"]ymodP當(dāng)N為奇數(shù)的情況下，則有：那么，結(jié)合前面討論的公式，對奇數(shù)情況下求模，則結(jié)果為如下等式：X^modP=[X(XX^N^]modP={X[(XmodP]/2J}modH綜合前面的兩種情況，我們可以發(fā)現(xiàn)，當(dāng)N為偶數(shù)時，我們可以求X的平方再取模，如果是奇數(shù)的話則要再乘以X，然后取模。這樣，一次運算下來，我們就將指數(shù)N折半了。按照這個過程，整個過程的時間復(fù)雜度可以降低到對數(shù)的級別上來。根據(jù)討論的遞歸關(guān)系，我們可以得出如下遞歸方式的代碼：Java代碼工，publicstaticlongpower(longx,longn,longp){if(n==0)return1;5.longtmp=power((x*x)%p,n/2,p);7.if(n%2!=0)tmp=(tmp*x)%p;10.returntmp;

12.}將遞歸版本轉(zhuǎn)換成循環(huán)實現(xiàn)的方式的代碼如下：Java代碼二publicstaticlongloopPower(longx,longn,longp){x%=p;longtmp=0;5.while(n>0){tmp=(x*x)%p;if(n%2!=0)tmp=(tmp*x)%p;n/=2;}13.returntmp;}問題2分析結(jié)合前面的情況，因為問題2中本身需要求模運算的數(shù)字比較特殊，不是用一個普通的數(shù)據(jù)類型來保存，而是用的整型數(shù)組或者字符串?dāng)?shù)組。在這種情況下，我們需要考慮的是利用一些模運算的特性，使得整個運算的過程拆分成可運算的各個小的步驟。在這里，我們先假設(shè)是10進制的數(shù)字，比如說一個int數(shù)組［1,2,3,4,5,6］，那么他們實際對應(yīng)的這個數(shù)字應(yīng)該是如下：123456=1X1Q51-2X104+3xW3+4x102+5x10L+6x10°這就相當(dāng)于轉(zhuǎn)換成了一個多項式求和的問題。對于一個整型的數(shù)組表示的長數(shù)據(jù)，我們按照多項式方式求和的典型代碼如下：Java代碼*1.publicstaticlongsum(int[]array)2.{3.longsum=0;4.for(inti=1;i<array.length;i++)5.{6.sum=sum*10+array[i];7.}8.returnsum;9.}如果再結(jié)合一些模運算的性質(zhì)來考慮，比如，對多個數(shù)字的相加再求模和先對中間部分結(jié)果求模再相加之后求模的結(jié)果是一樣的。那么，我們可以得出一個通用的求模運算的方法：Java代碼工

1.publicstaticlongsum(int[]array,intbase,intp)1.TOC\o"1-5"\h\z{longsum=0;for(inti=1;i<array.length;i++)\o"CurrentDocument"{sum=sum*base+array[i];sum%=p;}returnsum;}這里，base表示數(shù)的進制，可以是10以外的其他進制?？偨Y(jié)：前面針對大整數(shù)的兩種情況進行了討論，一種是給定一個整數(shù)，然后有一個比較大的指數(shù)，這種情況下需要考慮將指數(shù)變小給降下來。這里要利用到模運算里底數(shù)可以結(jié)合的特性。而針對一個很長的整數(shù)，我們可以將他轉(zhuǎn)換成多項式求和的形式。這里就利用了多個數(shù)字求和取模和部分結(jié)果先取模再求和取模的結(jié)果一致這個特性。問題本身不是很復(fù)雜，主要是要把這幾種特性想清楚，給用好了。總的來看，確實有點繞。補充證明：我們先來證明如下的等式成立：(X?￥)modF^[X(丫modP)]modJ,=[(XmodP).(YmodP)]modP因為X,Y都要對P求模，而實際上X,Y都可以表示成X=A*P+B的形式，其中B就是XmodP的結(jié)果。那么前面的A*P這部分則是對于P可整除的。(X*Y)=(A*P+B*Y=A*P*Y+B*Y如果對這個等式的右邊求模的話，顯然A*P*Y這一部分是P的倍數(shù)，求模后的結(jié)果為0，則結(jié)果為(B*Y)modP，前面我們知道B=XmodP。這樣我們就證明了(X*Y)modP=[X(YmodP)]modeP后面這部分的證明可以類似推導(dǎo)出來。我們再證明下面的等式成立：XNmodF=(XmodP)NmodP按照前面一部分的討論，我們可以假設(shè)X=A*P+B那么原來的等式則轉(zhuǎn)化為：X"皿dmWxF+WmodF在右