ღゝ◡╹)ノ❤️

集中一点,登峰造极!

  menu
137 文章
0 浏览
0 当前访客
ღゝ◡╹)ノ❤️

算法小结8-快速幂求余

题目链接🔗

get:

根据算数集合均值不等式,如果几个数的总和一定,那么这几个数相等的时候最大。

image.png

所以可以将原题抽象成求x的a次方,然后推导

image.png

然后转化为求最大值的问题,接着求导就可以了。

得出结论,当x = 3的时候是最大值。

快速幂求余

公式:

image.png

推导:

求余的本质就相当于填“格子”,比如(4^2)%3,

如果不用快速幂求余,就相当于这样想,一个一个填到最后,空的格子便是余数:

如果用快速幂求余相当于这样想,先一行一行的填格子也就是((4%3)*4)%3:

括号里的(4%3)含义相当于把左边三列给消灭了,所以还可以写成(1*(4%3))%3,也就是((4%3)*(4%3))%3;

得到这个结论就容易往下推了,如果求(x^n)%p,那么:

(x^n)%p=>((x^2)^(n/2))%p //就相当于n/2个x^2相乘,

=>((x^2%p)^(n/2))%p

这个是n是偶数的情况,如果是奇数要写成:(x*(x^2%p)^(n/2))%p

再看大佬写的题解:

int p = 1000000007;
long x = 3, sum = 1;
for (int i = n / 3 - 1; i > 0; i /= 2) {
   if (i % 2 == 1) sum = (sum * x) % p;
   x = (x * x) % p;
}

i /= 2就相当于n/2就相当于x^x。

时间复杂度从O(n)变成O(log2(n))。


标题:算法小结8-快速幂求余
作者:哇哇哇哇
地址:https://wuxiangshi.vip/articles/2021/12/09/1639056392681.html