幂取模

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实现的。。。。看不到算法,一直很纠结,直到今天晚上翻紫书看到了这个。真可谓众里寻他千百度,蓦然回首,那人却在灯火阑珊处。

  • 发表于:
  • 原文链接:https://kuaibao.qq.com/s/20180816G1X33E00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券