幂取模

python内置了一个pow()函数，可以快速求幂数

不过，有时候我们并不需要最终的结果，可能只是需要结果对一个数取模的结果，当然这个python内置函数也可以满足你

这个结果出来的很快的，比你

这样要快很多很多。。。懒，没去测具体时间。

这也说明了一个事情，那就是，这里有一个算法，可以快速求出这个式子的结果

呼，终于引出主角了。

如果你没有了解过python也没啥，上面就当**，直接跳过，下面才是重点干货。 空两行，以示尊敬。

题目：

输入正整数a,b,c，输出modc的值。

我们很快就能写出这样的代码，这就是上面那个想法的C语言实现。不过，就要面临一个十分棘手的问题。如果a，b大一点，那么ab的结果必然越界，就算是long long类型也无事于补。这说明要想其他办法了。

如果你知道一个公式，那就好办了。

xy mod z = (x mod z)(y mod z) mod z

知道了这个公式，我们就能修改上面代码了。

OK了，不管你a，b是什么数量级，我这个肯定是不会越界的，逻辑也没问题，万事大吉了。不过，算法肯定要考虑复杂度呀，很明显时间复杂度O(n)。当n很大的时候，太费时了，我们需要优化。

我们可以采用分治法。

这样，时间复杂度直接降到O(logn)。完美了

算法部分整理至紫书。

啊，纠结了我三四个月的东西终于解决了，你们不知道我有多烦，一直想不明白python内置函数pow()的实现方法，按照其他人的指引，用PyCharm看实现源码，很明显python告诉了我，这个函数我是用C实现的。。。。看不到算法，一直很纠结，直到今天晚上翻紫书看到了这个。真可谓众里寻他千百度，蓦然回首，那人却在灯火阑珊处。