썸네일 출처: https://ye-yo.github.io/thumbnail-maker/

📖 문제

1629번: 곱셈
분할정복을 이용해서 곱셈의 계산 횟수를 줄이는 문제

💡 아이디어

1. 분할정복 활용

10을 11번 곱하는 계산을 단순하게 하면 총 10번의 계산이 필요하다. 시간복잡도로 표현하면 O(n)이다. 하지만 곱하기를 절반으로 나눠서 10을 5번 곱한것과 10을 6번 곱한것의 곱으로 나누고, 각각을 또 절반으로 나누기를 반복하면 시간복잡도는 O(logn)이 된다.

2. A*B 를 C로 나눈 나머지를 각각을 C로 나눈 나머지로 구하기

모든 곱솀을 계산한 뒤 나머지를 구하려고 하면 곱셈 결과가 너무 커진다.
a와 b를 곱한 것의 나머지는 a의 나머지와 b의 나머지를 곱한 것의 나머지와 같다. 이걸 이용하면 계산값의 크기가 지나치게 커지는 것을 막을 수 있다.

✏️ 코드

use std::io::{stdin, prelude::*};

fn solve() {
    let mut input = String::new();
    stdin().read_to_string(&mut input).unwrap();
    let mut input = input.split_ascii_whitespace().flat_map(str::parse::<usize>);

    let (a, b, c) = (input.next().unwrap(), input.next().unwrap(), input.next().unwrap());

    let mut split = b;
    let mut sub_result = a % c;
    let mut leftover = 1usize;

    while split > 1 {
        if split % 2 == 1 {
            leftover = (leftover * sub_result) % c;
        }
        sub_result = (sub_result * sub_result) % c;

        split /= 2;
    }

    println!("{}", (sub_result * leftover) % c);
}