백준(C++) 1629 [곱셈]

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

접근방법

분할 정복을 이용한 거듭 제곱 문제이다. 입력 조건은 A, B, C는 모두 2,147,483,647 이하의 자연수이고, 이를 단순 계산할 시 오버플로우 또는 시간초과가 난다.(int 형 21억 언저리, long long 형 시간초과) 그러므로 다른 방법으로 접근해야한다.

long long 형을 쓰고 재귀를 사용한 거듭제곱을 사용하면 오버플로우와 시간초과 둘다 잡을수있다.

필요한 기본 수학 지식은 기본 지수법칙이다.

 a^b  = a^(b/2) * a^(b/2)

이를 이용하면  ll xx함수에서 a,b,c를 받아들이면 b가 1일때 그냥 계산으로 넘어가고

2이상일 경우 재귀로 작동하게 했다.

중간에 result = result * result % c;에서 위의 공식을 이용했고

마지막에 짝수일경우엔 이 공식으로 끝나고 홀수일경우 한번더 곱해주는걸로 끝냈다.

 

다음은 코드이다.

#include<iostream>
using namespace std;
using ll = long long;

ll xx(ll a, ll b, ll c){
if(b == 1) return a % c;
ll result = xx(a,b/2,c);
result = result * result % c;
if(b % 2 == 0) return result;
return result * a % c;
}

int main(void){
    cin.tie(0);
	ll ix,iy,iz;
	cin >> ix >> iy >> iz;
	cout << xx(ix,iy,iz);
    return 0;
}