Java教程

QQQ快速幂

本文主要是介绍QQQ快速幂，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

很显然超时了

//平方次数要考虑0次； 
#include<stdio.h>
typedef long long ll;
int main()
{
	ll a,b,p;
	scanf("%lld %lld %lld",&a,&b,&p);
	if(b==0) printf("%lld\n",1%p); 
	else 
	{
		for(int i=1;i<b;i++){
		a*=a;
		a%=p;
		}
		printf("%lld\n",a%p);
	}
	return 0;
 }

优化之后的 

//平方次数要考虑0次； 
//学习了位运算>>   <<
#include<stdio.h>
typedef long long ll;
ll a,b,p,res=1;
int main()
{
	scanf("%lld %lld %lld",&a,&b,&p);
	if(b==0) printf("%lld\n",1%p); 
	else 
	{
		while(b){
			if(b&1) res=res*a%p;
			a=a*a%p;
			b>>=1;	
		}
	printf("%lld\n",res%p); 		
	}
	return 0;
 }
这篇关于QQQ快速幂的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航