哈嘍各位親愛的觀眾朋友大家好！今天我們來(lái)了解一下分治算法。

分治，解釋為“分而治之”，意為將一個(gè)大的問題分成更多的小問題來(lái)解決。憑著簡(jiǎn)簡(jiǎn)單單的一句話讓大家去馬上做題肯定是不太現(xiàn)實(shí)的，那么就讓我們通過今天的幾道基礎(chǔ)題，來(lái)學(xué)著用一下分治。讓我們點(diǎn)開下面的音樂，開啟今天的內(nèi)容吧！

首先感謝各位的支持。上一期我的文章閱讀量超過了30 。我也兌現(xiàn)我的承諾，把程序放到洛谷的數(shù)據(jù)里評(píng)測(cè)了一下下

今天的題是“快速冪”：

輸入b，p，k的值，求b^p mod k的值。其中b，p，k為整型數(shù)。

這~~~我一看就懵了 。b^p我還能勉強(qiáng)理解，請(qǐng)問你給寫個(gè)mod是什么意思？我網(wǎng)上一查，原來(lái)是昨天（誤）原來(lái)mod的含義是C++常說(shuō)的百分號(hào)。

這道題目本身不難，要滿足這么大的數(shù)據(jù)規(guī)模就很難了。但是，求余的話我們不是可以試著把已經(jīng)被整除掉的數(shù)據(jù)抹去，再依據(jù)a^n=a^((n/2)*2)(a%2==0)或者a^n=a*(a^((n/2)*2))(a%2!=0)的數(shù)學(xué)性質(zhì)，將a^n一步步的分解開來(lái)，然后逐級(jí)乘方不久完了嘛！整體而言這樣的計(jì)算復(fù)雜度應(yīng)該是 θ(log(p))，這樣我的電腦就能接受了。

感覺題解和思路的數(shù)學(xué)味兒是不是重了很多？這大概就是未來(lái)算法的特點(diǎn)了。我也想說(shuō)，咱這哪是信競(jìng)啊，分明是數(shù)學(xué)競(jìng)賽計(jì)算機(jī)考試好不好！解決了這道題，我想順帶說(shuō)一下，記得我們的函數(shù)必要時(shí)一定要有return！該結(jié)束的遞歸或者DFS一定不能讓它再運(yùn)行下去。別問我咋知道的（捂臉），不然程序分分鐘死遞歸超時(shí)！

這還是一個(gè)比較入門的數(shù)學(xué)問題。我覺得我可以留一個(gè)堆排序的作業(yè)，提醒一下，BNDSOJ上的堆排序題測(cè)試數(shù)據(jù)開頭都是150000，不要想著用老實(shí)算法騙分哦！

題目：

給定n(1≤n≤150000)個(gè)數(shù)，每個(gè)數(shù)在-10^9到10^9之間(包含邊界)，用堆排序?qū)⑺麄兩蚺判颉?/span>

輸入、輸出描述：

第一行輸入一個(gè)n，表示有n個(gè)數(shù)，接下來(lái)一行n個(gè)整數(shù)。

輸出一行，將這n個(gè)整數(shù)從小到大輸出，每個(gè)整數(shù)之間用一個(gè)空格隔開。

示例輸入：

8
-4128 8544 13928 15221 -6654 9127 5532 9123

示例輸出：

-6654 -4128 5532 8544 9123 9127 13928 15221

好啦，今天的文章到這里就結(jié)束啦。喜歡的話記得一鍵三連~~下一期在更新題解的基礎(chǔ)上還會(huì)講一道新的題。同時(shí)我們文章開頭的音樂欄目也歡迎大家來(lái)點(diǎn)歌推薦好聽的純音樂。我們下一期再見啦！