백준 1629번 곱셈 ( C++ )

문제

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

1629번: 곱셈

 

해설

A,B,C의 크기를 보고 long lnog 자료형을 써야했던 문제임을 파악해야했음

횟수를 줄이기 위해 재귀 방식 채택

코드

#include<bits/stdc++.h>
 
using namespace std;
long long A,B,C,ret;
 
long long cal(long long a,long long b){
    if(b==1) return a%C;
    
    if (b%2) return cal(a,b/2)*cal(a,b/2)%C*a%C;
    else return cal(a,b/2)*cal(a,b/2)%C;
}
 
int main(){
    cin >> A >> B >> C;
    
    cout << cal(A,B);
}