[C++知识库]杭电2035(C++)

杭电2035

题目

AC代码

#include<iostream>
using namespace std;
int quer(int a,int b)
{
	int ans;
	if(b==0) ans=1;
	else
		{	
			int sum=a*a;
			if(sum>1000) sum=sum%1000;	
			ans=quer(sum,b/2);
			if(b%2==1) 
			{	
				if(ans>1000) ans=ans%1000;
				ans=a*ans;
			}
		}
	return ans;
}
int main()
{
	int a,b,answer;
	while(1)
	{
		cin>>a>>b;
		if(a==0&&b==0) break;
		answer=quer(a,b)%1000;
		cout<<answer<<endl;
	}
	
	return 0;
 } 

题目思路

求出幂积再运算
利用%1000获取后三位
采用递归求幂积

出现问题

较大的数字幂积会爆掉
解决方法：计算过程中及时取余以减少数字量
注意：递归里正向计算的时候要及时取余，反向运算的时候也要及时取余，二者缺一不可