都是数学题！都是数学题！

哈喽各位亲爱的观众朋友大家好！今天我们来了解一下分治算法。

分治，解释为“分而治之”，意为将一个大的问题分成更多的小问题来解决。凭着简简单单的一句话让大家去马上做题肯定是不太现实的，那么就让我们通过今天的几道基础题，来学着用一下分治。让我们点开下面的音乐，开启今天的内容吧！

首先感谢各位的支持。上一期我的文章阅读量超过了30 。我也兑现我的承诺，把程序放到洛谷的数据里评测了一下下

今天的题是“快速幂”：

输入b，p，k的值，求b^p mod k的值。其中b，p，k为整型数。

这~~~我一看就懵了 。b^p我还能勉强理解，请问你给写个mod是什么意思？我网上一查，原来是昨天（误）原来mod的含义是C++常说的百分号。

这道题目本身不难，要满足这么大的数据规模就很难了。但是，求余的话我们不是可以试着把已经被整除掉的数据抹去，再依据a^n=a^((n/2)*2)(a%2==0)或者a^n=a*(a^((n/2)*2))(a%2!=0)的数学性质，将a^n一步步的分解开来，然后逐级乘方不久完了嘛！整体而言这样的计算复杂度应该是 θ(log(p))，这样我的电脑就能接受了。

感觉题解和思路的数学味儿是不是重了很多？这大概就是未来算法的特点了。我也想说，咱这哪是信竞啊，分明是数学竞赛计算机考试好不好！解决了这道题，我想顺带说一下，记得我们的函数必要时一定要有return！该结束的递归或者DFS一定不能让它再运行下去。别问我咋知道的（捂脸），不然程序分分钟死递归超时！

这还是一个比较入门的数学问题。我觉得我可以留一个堆排序的作业，提醒一下，BNDSOJ上的堆排序题测试数据开头都是150000，不要想着用老实算法骗分哦！

题目：

给定n(1≤n≤150000)个数，每个数在-10^9到10^9之间(包含边界)，用堆排序将他们升序排序。

输入、输出描述：

第一行输入一个n，表示有n个数，接下来一行n个整数。

输出一行，将这n个整数从小到大输出，每个整数之间用一个空格隔开。

示例输入：

8
-4128 8544 13928 15221 -6654 9127 5532 9123

示例输出：

-6654 -4128 5532 8544 9123 9127 13928 15221

好啦，今天的文章到这里就结束啦。喜欢的话记得一键三连~~下一期在更新题解的基础上还会讲一道新的题。同时我们文章开头的音乐栏目也欢迎大家来点歌推荐好听的纯音乐。我们下一期再见啦！