백준 1629 곱셈 / C++

문제 : 1629

풀이 point

지수법칙을 활용하는 문제이다. $a^b * a^b = a^(2b)$이다. 라는 수학적 성질을 통해 숫자들을 분할하여 곱셈을 진행한다.

풀이 방법

b == 1일때는 아무런 곱셈도 진행하지 않고 A를 return 한다.
그 외에는 b가 1이 될때까지 recur(b/2)를 호출한다. 단 b가 홀수면 A를 한번 더 곱해준다.

코드

//백준 1629, 곱셈

#include <iostream>

long long A, B, C;

long long recur(long long b){
    if(b == 1) return A%C;
    long long pow = recur(b/2)%C;
    if(b % 2 != 0) return ((pow * pow) % C * A) % C;
    else return (pow * pow)%C;
}

int main (){

    std::cin >> A >> B >> C;
    std::cout << recur(B);

    return 0;
}

2025-02-11T01:38:50.755Z