算法竞赛--快速幂

快速幂

1.给定三个正整数a,b,m(a<1e9,b<1e6,1<m<1e9),求aexpb%m. (循环求解)

时间复杂度为O(b)

参考代码:

#include<stdio.h>
int main()
{
	long long a,b,m,ans=1;
	scanf("%lld%lld%lld",&a,&b,&m);
	for(int i=0;i<b;i++)
		ans=ans*a%m;
	printf("%lld",ans);
	return 0;
}

2.给定三个正整数a,b,m(a<1e9,b<1e18,1<m<1e9),求aexpb%m. (递归求解)

时间复杂度为(O(logb))

思路:如果b是偶数aexpb=aexp(b/2)aexp(b/2)，否则如果是奇数,aexpb=aexp(b)aexp(b-1)，b是奇数的情况，则在下一步转换可以转换为偶数的情况。

参考代码如下:

#include <stdio.h>
typedef long long ll;
ll ff(ll a,ll b,ll m)
{
	if(b==0)
		return 1;
	if(b%2)
		return a*ff(a,b-1,m)%m;
	else
	{
		ll mul=ff(a,b/2,m);
		return mul*mul%m;
	}
}
int main()
{
	ll a,b,m;
	scanf("%lld%lld%lld",&a,&b,&m);
	printf("%lld",ff(a,b,m));
	return 0;
}

上面代码中,条件if(b%2)可以用if(b&1)代替,这是因为b&1进行位与运算,判断b的末尾是否为1,因此当b为奇数时b&1返回1，if条件成立，这样写执行速度会快。

另外注意: (1).如果初始时a有可能大于等于m,那么需要在进入函数前就让a对m取模.

(2).如果m为1，可以直接在函数外部特判为0，不需要进入函数计算。

3.给定三个正整数a,b,m(a<1e9,b<1e18,1<m<1e9),求aexpb%m. (迭代求解)

思路:可以将b转换为二进制来计算。

参考代码如下:

#include <stdio.h>
typedef long long ll;
int main()
{
	ll a,b,m,ans=1;
	scanf("%lld%lld%lld",&a,&b,&m);
	do{
		if(b%2)
			ans=ans*a%m;
		a=a*a%m;
		b=b/2;
	}while(b>0);
	printf("%lld",ans);
	return 0;
}