[백준] 1629번 _ 곱셈 풀이

 


1. 문제

https://www.acmicpc.net/problem/1629

2. 풀이

2.1. 비효율적인 풀이

  • 제곱수를 짝수일 경우 2개로 나누고, 홀수일 경우 짝수, 홀수 자식으로 만들어서 재귀함수를 호출합니다.
  • 아래의 소스코드는 자식이 많아지는 경우에 시간 초과가 납니다.
  • 메모이제이션이나 2.2의 문제풀이 방법을 참고해주세요.
#define _CRT_SECURE_NO_WARNINGS
#include<algorithm>
#include<iostream>
using namespace std;
int a, b, c;
long long pow(int x, int y, int z) {
	if (y == 1) 		    return x % z;
	if (y % 2 == 0) 		return (pow(x, y / 2, z) * pow(x, y / 2, z)) % z;
	else            		return (pow(x, y / 2, z) * pow(x, 1 + y / 2, z)) % z;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> a >> b >> c;
	cout << pow(a, b, c);
}

2.2. 효율적인 풀이

  • 제곱수를 짝수일 경우 절반으로 떨어뜨리는 방법을 사용하고, 홀수일 경우 짝수로 만들어서 속도를 매우 빠르게 할 수 있습니다.
#include<iostream>
using namespace std;
long long int a, b, c;
long long int pow(long long int x, long long int y){
   if(y==0) return 1;
   if(y==1) return x;
   if(y % 2 == 1) return (pow(x, y-1)*x) % c;
   long long int half = pow(x, y/2);
   return (half * half) % c;
}
int main(){
   cin>>a>>b>>c;
   cout<<pow(a,b)%c;
   return 0;
}