백준 1629번 : 곱셈

곱셈

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

힌트

레퍼런스 [1]을 참고했다.

• 지수 법칙 : $a^{n+m}=a^n\ast a^m$
• 모듈러 성질 : $(a\ast b)$%$c$ = $(a$%$c\ast b$%$c)$%$c$
• 재귀 함수
• key hint : 분할 정복

Code

#include <iostream>

using namespace std;

int a, b, c;

long long int F(long long int y){
    if(y==1) return a%c;

    long long int k = F(y/2)%c;

    if(y%2==0) return k*k%c;
    else return k*k%c  *  a%c;
}

int main() {
    scanf("%d %d %d", &a, &b, &c);
    cout << F(b) << endl;
    return 0;
}

재귀 함수

long long int F(long long int y){
    if(y==1) return a%c;

    long long int k = F(y/2)%c;

    if(y%2==0) return k*k%c;
    else return k*k%c  *  a%c;
}

핵심 파트는 재귀 함수 부분이다.

Divide and Conquer 문제를 해결하기 위해 재귀를 사용해야 한다.

직관적으로 이해가 안 돼서 너무 힘든 부분..

중간에 있는 k를 return 쪽에 대입해 보면 지수법칙과 모듈러 법칙이 적용된 게 보인다.

짝수인 경우 : $(F(\frac{y}{2})$%$c\ast F(\frac{y}{2})$% $c)$%$c$

홀수인 경우 : $(F(\frac{y}{2})$%$c\ast F(\frac{y}{2})$% $c)$%$c\ast a$%$c$

 

그런데 만약 이렇게 했다면 재귀호출이 너무 많이 발생해서 최대 입력에서 실패했다고 한다. [2]

무튼 중복 재귀호출을 최대한 피하고자 중간에 k라는 변수를 통해 재귀를 받아주고 있는 것..

레퍼런스

[1]

[백준] 1629번 : 곱셈 [C/C++]

[2]

BOJ - 1629 곱셈 해결 전략 (C++)