\ # 쾌속 멱 알고리즘

말 그대로 빠 른 멱 은 빠르게 밑 수 를 계산 하 는 n 차 멱 이다.그 시간 복잡 도 는 O (log ₂ N) 로 소박 한 O (N) 에 비해 효율 이 크게 향상 되 었 다.그 기본 원 리 는 다음 과 같다. ab 로 초보적인 소 개 를 한다. 우 리 는 먼저 b 를 2 진수 로 바 꾸 면 이 2 진법 의 i 위 권 은 2i - 1 e. g. a11 = (a2) 0 + (a2) 1 + (a2) 3 이 고 11 의 2 진 은 1011 so: 11 = 23 * 1 + 22 * 0 + 21 * 1 + 20 * 1 이기 때문에 우 리 는 이상 의 전환 이 있 었 다. a11 = (a2) 0 + (a2) 1 + (a2) 3
몇 시 보급:

b & 1// b       ，   1    ，    1，    0，       
b>>1// b        ，            

다음은 완전한 코드 블록 으로 보 여 드 리 겠 습 니 다.

#include
#define ll long long
using namespace std;
void quick_power(int x,int y){ 
	int ans=1;
	while(y){//  y      
		if(y&1==1) ans*=x;// y and 1   1 ，ans=ans*x
		x=x*x;
		y>>=1;//y      （         ）
	}
	cout<<ans<<endl;
}

int main()
{
	void quick_power(int x,int y);
	ll a,b;
	cin>>a>>b;
	quick_power(a,b);
	return 0;
}

이상 은 빠 른 속도 계산법 의 가장 기본 적 으로 자주 사용 되 는 형식 으로 바 이 너 리 연산 과 관련 되 며 비 재 귀 판 에 속한다.