快速幂运算模板（求n^k以及前几位或后几位）

计算n^k的结果

步骤：

1.把n由十进制转换为二进制，按二进制来计算（最后结果还是一样的）

2.把n由二进制转换为2^k相加的形式

先举个例子：

求5^22：

接着就可以很好地理解了

O(logn)计算幂运算的算法：

//无mod单纯求n^k
 
#include<stdio.h>

typedef long long ll;

ll mod_pow(ll x,ll n)
{
	ll res=1;
	while(n>0)
	{
		if(n&1) res=res*x;
		x=x*x;
		n>>=1;
	}
	return res;
}

int main()
{
	ll x,n;
	while(~scanf("%lld%lld",&x,&n))
	{
		printf("%lld\n",mod_pow(x,n));
	}
	return 0;
}

以上只是单纯的求n^k，那么很可能有某一中间结果超限或者题目要求输出对某个数取模的结果，这时我们可以稍作修改：

//对mod取模 
 
#include<stdio.h>

typedef long long ll;

ll mod_pow(ll x,ll n,ll mod)
{
	ll res=1;
	while(n>0)
	{
		if(n&1) res=res*x%mod;//计算的每一步都对mod取模防止超限 
		x=x*x%mod;//计算的每一步都对mod取模防止超限 
		n>>=1;
	}
	return res;
}

int main()
{
	ll x,n,mod;
	while(~scanf("%lld%lld%lld",&x,&n,&mod))
	{
		printf("%lld\n",mod_pow(x,n,mod));
	}
	return 0;
}

理解了快速幂的原理后也可以用递归实现：

当n为偶数时有x^n=((x^2)^(n-2))，递归转为n/2的情况。n为奇数时有x^n=((x^2)^(n/2))*x，同样也可以递归转为n/2的情况。这样不断递归下去，每次n都减半，于是可以在O（logn）时间内完成幂运算。（《挑战程序设计竞赛P123》）

代码实现：

#include<stdio.h>

typedef long long ll;

ll mod_pow(ll x,ll n,ll mod)
{
	if(n==0) return 1;
	ll res=mod_pow(x*x%mod,n/2,mod);//这里n/2等价于n>>=1 
	if(n&1) res=res*x%mod;
	return res;
}

int main()
{
	ll x,n,mod;
	while(~scanf("%lld%lld%lld",&x,&n,&mod))
	{
		printf("%lld\n",mod_pow(x,n,mod));
	}
	return 0;
}

拓展：

我们可以求n^k的前几位或后几位。

后几位相对简单，如果要求后三位则直接设mod=1000，即mod_pow(n,k,1000)。得出的就是后三位

那如何求n^k的前a位呢？

 先看下这道题：

lightoj 1282 Leading and Trailing（求n^k的前三位后三位）