백준 01629 - 곱셈

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

1629번: 곱셈

 

고려사항

• 10830번 행렬의 거듭제곱 구하기 처럼 분할정복을 이용하여 곱셈의 연산 수를 줄이는 방식
• long long 의 거듭제곱을 위해 powl( ) 사용.
• 결과(ans), 지수(b) 와 현재 거듭제곱(tmp)이 있을 때,
  1) 지수  % 2 == 1, 이라면 ans 에 tmp를 곱해준다.
  2) 지수를 반토막 내준다.
  3) tmp를 제곱해준다.
   

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int a, b, c;
    long long tmp, ans = 1;
    cin>>a>>b>>c;

    tmp = a;
    while(b > 0){
        if(b % 2 == 1){
            ans = (ans * tmp) % c;
        }

        b /= 2;
        tmp = (long long)powl(tmp, 2) % c;
    }

    cout<<ans;
    return 0;
}