快速幂
快速幂
对于线性求解的问题,如果需要优化,很多时候可以考虑选用树型结构的数据结构或者分治思想,那样可以把时间复杂度从O(n)降低到O(logn).这里我们考虑用分治思想.
a的b次方,其实很容易想到,若b是偶数,则a的b次方=a的b/2次方a的b/2次方a(这里的b/2去取下整).即我们只要求处出a的b/2,然后再经过一次乘法运算,即可求出a的b次方.继续将b/2分解成b/4,b/8......最终b会变成1,并且只需要logn次就可以将b变成1我们称这种快速计算幂的方法称为快速幂算法.
[快速幂求(a^b)%n---代码实现递归方法]
```int quickPow(int a,int b,int n)
{
if(b==1)
return a;
if(b%2==0)
{
//b是偶数
int =quickPow(a,b/2,n);
return t*t%n;
}
else
{
//b是奇数
int t=quickPow(a,b/2,n);
t=t*t%n;
t=t*a%n;
return t;
}
}[快速幂求(a^b)%n---代码实现非递归方法]
{
int ret=1;
while(b)
{
if(b%2==1)
ret=ret*a%n;
a=a*a%n;
b=b/2;
}
return ret;
}例题:序列的第K个数
[问题描述]
BSNY在学等差数列和等比数列,当已知前三项时,就可以知道是等差数列还是等比数列.现在给你序列的前三项,这个序列要么是等差数列,要么是等比数列,你能求出第K项的值;如果第K项太大,对其取模200907.[输出格式]
对于每组数据,输出第K项取模200907[样例输入]
2
1 2 3 5
1 2 4 5[样例输出]
5
16[数据规模]
1<=T<=100
1<=a<=b<=c<=10^9
0<k<=10^9;[思路点拨]
对于等差数列,比较好判断,如果ai+ai+2=ai+1*2,就为等差数列,根据通项an=a1+(n-1*d就可以求出第n项.对于等比数列,同样比较好判断,但求第n项时,an=a1*q^(n-1), 求q的第n-1次幂,需要使用快速幂.