快速幂

我觉得这个东西还是比较简单的，为什么考试的时候没有打出来我也不知道，再次奠基一下我那凉掉的考试。
这里是一个简单的快速幂算法，求2的n次方的。

这里在放一道例题：
P1226 取余运算||快速幂

下面是源代码：

#include<cstdio>
using namespace std;
int n;
long long  search(int n)
{
	//if(n==0) return 1;
	if(n==1)
	{
		return 2;
	}
	else
	{
		if(n%2==0)
		{
			return search(n/2)*search(n/2);
		}
		else
		{
			return search(n/2)*search(n/2)*2;
		}
	}
}
int main()
{
	scanf("%d",&n);
	printf("%d",search(n));
	return 0;
}

□

上面这个是“证毕”的符号！
长知识了吧！

但是上面这个写法是不标准的，因为这样写search每次会被重新算一次，所以说要定义一个变量来存储，下一次search算的一个值，这样可以大大的节省时间！！！

代码大致实现：(函数中那个部分，省略函数的头头和尾巴没有写！)

    if(n==0) retrun 1;
	long long basic;
    basic=search(a,n/2,k);
    if(n%2) return basic*basic*a;
    else return basic*basic;
    

2018.7.24

其实用递归来实现快速幂是一件非常慢的事情，所以说真正的快速幂应该是使用递推来实现的，下面就放一个递推版的快速幂：

LL fpow(LL x,LL k){LL v=1;
	while(k){
		if(k&1)v=v*x%p;
		k>>=1,x=x*x%p;
	}return v;
}