大整數乘法：給出a,b,求a*b。a，b<10^10000

(1)用手算乘法的方式，O(nm)。

(2)分治乘法·對於兩個長度為n的數a.b，令m=n/2.則可以將a.b表示為：

a=a1×10^m+a2，b=b1×10^m+b2.其中a2.b2<10^m。

·那麼a×b=a1×b1×10^2m+（a1×b2+a2×b1）×10m+a2×b2.

·遞歸地計算A=a1×b1.B=a2×b2.C=（a1+a2）×（b1+b2），則a×b=A×10^2m+（C-A-B）×10m+B。

·我們將計算兩個長度為n的數的乘積的問題，轉化為了3個計算長度為n/2的數的子問題，並用O（n）時間合併答案。

·給出a，b，p.求a^b mod p。

·a.b.p≤10^9 （冪運算）

（分塊）·令m=根b,先算出d=a^m。

·設b=mx+c，c

·於是可以在O（根b）時間內計算出答案。

·還有更高效的做法嗎？

（分治）·對b的奇偶性進行討論。

·若b為偶數，則a^b=（a^（b/2））^2，遞歸地計算a^（b/2）即可。

·若b為奇數、則a^b=（a^((b-1)/2)）^2×a.遞歸地計算a^((b-1)/2即可。

·複雜度為O（logb）。

·有形如：ax^3+bx^2+cx+d=0這樣的一個一元三次方程。給出該方程中各項的係數（a.b.c.d均為實數）.並約定該方程存在三個不同實根（根的範圍在-100至100之間）.且根與根之差的絕對值≥1。

·要求由小到大依次輸出這三個實根，精確到小數點後2位。

·枚舉[-100，100]內的所有整數x，先判斷[x，x+1]內是否存在根。如果存在，問題就是在這個區間內找到這個根。

·假設現在要在區間[L，R]內找到一個根.取mid=(l+r)/2.計算f（micd）即可判斷根是在

[L,mid]中還是[mid,R]中，於是轉化為一個區間長度減半的子問題。·當R-L<10^-3時，精度已經符合題目要求，取(l+r)/2作為根即可。當題目精度要求增加時，該算法運行時間不會顯著增大。

注意到這裡的分治每次只會出現一個子問題，且子問題規模減半。樣的分治一般稱為二分法。

·對於兩個串長度為n的字符串S，T，稱這兩個串是“等價的，當且僅當滿足以下條件中的一個：

-1）n為奇數，且S和T完全相同。

·2）n為偶數，且此時如果將S切成長度相等的兩段S1.S2.將T切成長度相等的兩段T1，T2.則滿足S1與T1是“等價的“且S2與T2是“等價的”，或者滿足S1與T2是“等價的“且S2與T1：是“等價的”。

-例如aaba”與“abaa”是等價的，因為“aa”與“aa“等價，且“ba”與“ab“等價。

·判斷兩個串是否是“等價的”，保證串長均不超過2×10^5。

·假設現在我們要求與S等價的最小字符串，進行討論：

·1）如果S的長度為奇數，要求的串就是S本身。

·2）如果S的長度為偶數，設S切成長度相等的兩半後變為S1和S2.則遞歸地分別求出與S1和S2等價的最小的串，假設分別為A1.A2.那麼與S等價的最小的串就是A1+A2與A2+A1兩者中較小的一個。

·於是我們可以將一個規模為n的問題劃分成兩個規模減半的子問題，並在O(n)時間內合併得到問題的解。

·複雜度T（n）=2T(n/2)+O(n)=O(nlogn)。

上半部分請參看：

學點乾貨整理，歡迎關注我們，每天進步一點點。

閱讀更多 學點乾貨 的文章

關鍵字: 算法 計算長度 先算出