백준 1629번 : 곱셈

문제 링크 : https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

 문제 설명 

를 구하면 된다

 

 

 알고리즘 

1 .  A B C 모두 int 형을 초과할 수있어서 long long 형으로 지정해야되고

2. 단순히 A를 B번곱하면 시간초과가 나기에 분할 정복으로 풀어야한다.

3. 2^4 = 4^2 이다 즉 B가 짝수이면 A^B  = (A^B/2)^2 이고 B가 홀수 이면 (A^B/2)^2*A 이다 이거 이용하면된다 .

 

 코드  

#include<iostream>
typedef long long ll;
using namespace std;
 
ll A, B, C;
 
ll func(ll a, ll b) {
    if (b == 1)return a % C;
    ll val = func(a, b / 2);
    val = (val * val) % C;
    if (b % 2)val = (val * a) % C;//b가 홀수.
    return val;
}
 
 
 
int main() {
    cin >> A >> B >> C;
    cout << func(A, B);
 
}