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

문제: www.acmicpc.net/problem/1629

1629번: 곱셈

 

 

문제풀이

 

재귀 함수를 이용하여 문제를 풀었다.

 

일반적인 반복문으로 풀면 a^b는 연산 횟수에 의한 시간초과나 a^b 값의 크기로 인한 오버플로우가 일어날 수 있다.

 

 

코드

#include <iostream>

using namespace std;

long long func(long long a, long long b, long long c){
    if(b==1)
        return a % c;

    long long val = func(a,b/2,c);
    val = val * val % c;

    if(b%2==0){
        return val;
    }
    else{
        return val * a % c;
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int a,b,c;
    cin>>a>>b>>c;

    cout<<func(a,b,c);

    return 0;
}

 

 

결과