[C++][BOJ 1629 곱셈] pow 연산 줄이기

문제 바로가기

pow를 직접 구현하는 문제이다.

 

가장 단순하게 for문 돌려서 구현하면 당연히 시간 초과가 나온다.

연산 횟수를 줄여야한다.

 

예를 들어 

$A^{4} = (A^{2})^2 $ : 짝수일때

$A^{5} = A * (A^{2})^2 $ : 홀수일때

이렇게 연산을 줄일 수 있다.

원래대로라면 $A^{4} $는 A*A*A*A로 연산이 총 3번이지만 2번으로 줄일 수 있게 된다. 

즉, log2N 으로 연산 횟수가 줄어든다.

이것을 pow함수로 구현해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll A,B,C;

void Input(){
	cin >> A>>B>>C;
}

ll pow(int b){
	if(b==0) return 1;
	
	ll tmp = pow(b/2);
	tmp = tmp*tmp%C;
	
	if(b % 2) return A*tmp%C;
	return tmp;
}

void Solution(){
	cout<<pow(B);
	
}
void Solve(){
	Input();
	Solution();
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	Solve();
}

 

 

 

 

참고

1629 질문(더 자세한 설명 있음.)  

[프로젝트 오일러]1^1 + 2^2 + 3^3 + ... + 1000^1000 의 마지막 10자리