쾌속 구 멱

HDU 2035 명 은 A ^ B 를 사랑 합 니 다 (이분 구 멱, 쾌속 구 멱):http://acm.hdu.edu.cn/showproblem.php?pid=2035 빅 데이터 사상 을 사용 하여 배열 에서 구하 기:
두 가지 쓰레기 방법:

#include <iostream>
#include <cstdio>
using namespace std;
int main(){

	int m,n;
	while(~scanf("%d %d", &m, &n))
	{
		if(m==0&&n==0)
			break;
		int a[3],b[3],c[3]={0,0,0},i;
		for(i=0;i<3;i++)
		{
			a[i]=b[i]=m%10;
			m=m/10;
		}
		n--;
		while(n--)
		{
			for(i=0;i<3;i++)
				for(int j=0 ; j<3;j++)
				{
					if(j+i<3)
					{
						c[j+i]=a[i]*b[j]+c[j+i];
						if(c[j+i]>9)
						{
							if(i+j+1<=2)
								c[i+j+1]=c[j+i+1]+c[j+i]/10;
							c[i+j]=c[j+i]%10;
						}
					}
				}
			b[0]=c[0],b[1]=c[1],b[2]=c[2];
			c[0]=c[1]=c[2]=0;
		}
		printf("%d
",b[2]*100+b[1]*10+b[0]);

	}
	return 0;
}

 

#include<iostream>
using namespace std;
int main()
{
		int m,n;
	while(scanf("%d %d", &m, &n)!=EOF)
	{
	
		if(m==0&&n==0)
			break;
		
		m=m%1000;
		int w=m;
		n--;
		while(n--){
		m=m*m%1000;
		}
		cout<<m<<endl;
	}
}

 
 
 상대 적 으로 아래 두 가 지 는 괜 찮 은 것 같 아 요. 이 건 빠 른 속도 의 하나 라 고 할 수 있 을 것 같 아 요.
이분 구멱

#include<iostream>
#include<cstdio>
using namespace std;

int main(){
	int a,b;
	int ans;
	while(~scanf("%d%d",&a,&b)){
		if(a==0&&b==0) break;
		a=a%1000;//    
		ans=1;
		while(b>0){ 
			if(b%2==1)//1.   ，          ans   2.b==1 ，              
				ans=(ans*a)%1000;//    
			a=(a*a)%1000;//    
			b=b/2;//1.    2.b==1 ，b/2=0,         
		}
		printf("%d
",ans);
	}
	return 0;
}

 
 
이분 구멱 (비트 연산)

#include<iostream>
#include<cstdio>
using namespace std;

int main(){
	int a,b;
	int ans;
	while(~scanf("%d%d",&a,&b)){
		if(a==0&&b==0) break;
		a=a%1000;
		ans=1;
		while(b>0){
			if(b&1)//       ，    if(b%2==1)
				ans=(ans*a)%1000;
			a=(a*a)%1000;
			b=b>>1;//        ，    b=b/2;
		}
		printf("%d
",ans);
	}
	return 0;
}

 
 
 
 
물론 빠 른 멱 은 수 에 만 쓰 이 는 것 이 아니 라 행렬 에 서 는 빠 른 멱 의 용법 도 사용 할 수 있다.
자세 한 내용 은 사이트 주소 참조:http://blog.csdn.net/error/404.html?from=http%3a%2f%2fblog.csdn.net%2fu014665013%2farticle%2fdetails%2f40452065