1629번

1629번 - 곱셈

이 문제는 A의 B 제곱을 O(N) 이 아닌 다른 방법으로 풀 수 있는가를 묻는 문제 같다.

A의 B 제곱은 for문이 아닌, 분할정복을 이용해서 풀 수 있다. (이진수를 응용해서도 풀 수 있다.)

또한 (A*B)%C = ((A%C)*(B%C))%C 라는 것을 알면 쉽게 문제를 풀 수 있다.

궁금한 점 => 질문게시판 확인

이 문제에서는 int 형 변수를 넘어가기 때문에 전부다 long long 처리 하면 편하다. 

내가 궁금한 점은 return 될 때, 결과값이 중요한 것인지, 과정에서 값이 중요한 것인지였다.

<정답 코드>

#include<iostream>
 
using namespace std;
 
int A, B, C;
long long calc(int a, int b)
{
    if (b == 0)
    {
        return 1;
    }
    else if (b % 2 == 0)
    {
        long long temp = calc(a, b / 2);
        return ((temp%C)*(temp%C))%C;
    }
    else
    {
        return ((a%C)*(calc(a, b-1)%C))%C;
    }
}
 
 
int main()
{
    
    cin >> A >> B >> C;
    cout << calc(A%C, B) % C << endl;
    
 
    return 0;
}