00:02
这节课讲快速密,快速密跟惩方差不多,出密就是快速密,最需要磨P,这样就能保证最后的结果不至于过大。九块寿明有两种方法。第一种方法是连乘,也就是A乘员。再乘以A乘以B,次A。这样就最后算出的结果就是A的B次方,当然实际计算每次成员都需要磨P的。这样就能保证最后中间结果也不至于过大,因为数值过大的时候计算是非常慢的。所以磨皮的作用是非常大的。这种方法的时间复杂度是一个OB。嗯,优点是简单直观,缺点是当B非常大的时候。
01:03
这个计算速度非常慢的,因此我们采用第二种方法。要禁止拆减法要禁止拆解是指拆解指数啊B。任何一个整数都可以表示二进制的形式,因此将指数的币转换成二进制数。然后电力二进制串从右往左边力。第一次的时候。如果第一位是一,那么结果就乘上于A。并并且磨皮。然后执行下一步制成。A的制成意思就是将A变成A的平方,当然也需要磨P。然后第二次跟你。
02:00
第二次便利,也就是二进制位的第二位,从右往左的第二位。就是如果唯一。那那么结果就是陈商业这到平方,所以算是成是还是陈商业。但是这个时候A就是A的平方。然后抹屁。然后这直径下一步操作A的自上,这个时候A实际上是A的平方,也就是A的平方乘以A的平方变成了A的四次方。然后磨皮。然后进行下一次的便利。需要便利多少次?那就是二进制出的位处。鉴定完成过后,最后返回结果。这种方法的时间复杂度是。第一个O那个B。这是一个多项式的实验算法。
03:03
这也是计算机的你梦寐以求的快速的算法。我们看一下视力。嗯,A的十三次方。13可以换算到二进制就是1101,也就等于八加四加一。是首先从右往左边里。第一位是一所一乘以A的一次方。然后零零我就不乘了,所以这个地方就乘以一。然后又碰到一,这个时候就乘以A的四次方。最后还是个一,所以乘以A的大次方,这样就把A的十三次方给计算出来了。我们看一下这种方法的代码。嗯,看一下。
04:00
这个刚开始是对A是磨P。这个地方也可以不不用磨皮的。然后循环币。这个这个是什么意思呢?这个就是B不等于零嘛,就是还是其实其本质就是分到二进制的位数了。因为因为每次便利过后,B需要除以二的。每每次变率除以二,一直到B等于零的时候就退出循环。第一次去玩,就是判断第一位。从右往左到一位,如果为一的话,那么结果就乘以A,然后A自乘就是A等于A乘以A。然后一直变脸这个。这个你里面的步骤是一样的。
05:03
这个软件里面。有专门的函数,求快出没。是泡泡的。537,也就是我的三次方毛七。最后的结果肯定是六。我们看一下。更远的代码。自定义的,快速的。最后的结果肯定也是六。The。电脑速度有点慢。等一下。我们看到最终的结果就是那个。根元里面还有一个就快速幂的函数,这是系统自带的。
06:05
我们可以看一下结果。我们可以看到。也是六。快出明的两种方法讲完了,但是我们还有一个注意一点。我们第一。底数A是可以磨P的,我们代码里面确实是磨P了。第一呢?必不不能磨屁。第第二点。如果平时叔叔。并且A和P这个式子最大公约数为一,也就是A和P负数。当然,一般情况也也是负数的。
07:03
那么B可以摸到P减一。我们我们看一下代码。这个注册的话代码。我们再看一下结果。我们看到是六。我们三加六。等于九。下面改成九,我们看一下结果是不是等于六。我们可以看到最后的结果确实是。那也就是说指数。它的周期是T减一,所以。所以需要抹P减一的,而不是P。
我来说两句