[백준] 1629번. 곱셈 (C++)

문제

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

 

풀이

[분할 정복]

 

🍏모듈러 연산 적용

(A×B)%C = ((A%C)×(B%C))%C

 

🍏분할 정보 적용 예시

A=10, B=11, C=12를 생각해 보자

10^11은 10^5 x 10^5 x 10 과 같다

10^5 는 10^2 x 10^2 x 10 과 같다

10^2 는 10^1 x 10^1 과 같다

이 방식을 이용한 것이다

코드

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
	
    //INPUT
    long long A, B, C;
    cin >> A >> B >> C;
	
    //CALCULATE
    long long result = 1;
    A %= C;
    
    while (B > 0) {
        if (B % 2 == 1) {
            result = (result * A) % C;
        }
        A = (A * A) % C; 
        B /= 2;
    }
    
    cout<<result<<"\n";
    return 0;
}