BOJ 1629

곱셈 성공

 

 

0.5 초 (추가 시간 없음)

128 MB

73704

19953

14691

26.303%

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제 입력 1 복사

10 11 12

예제 출력 1 복사

4​

거듭제곱 분할정복 문제이다.

이문제가 기본형이라고 보면 된다.

 

마지막에 또 나머지 연산 해주는걸 잊지 말자!

 

#include <iostream>
using namespace std;
long long A, B, C;
void func(int power){
    if(power == 1)
        return;
    if(power%2 == 0){
        func(power/2);
        A = (A*A)%C;
    }else{
        long long oriA = A;
        func(power-1);
        A = A*oriA%C;
    }
}
int main(){
    cin>>A>>B>>C;
    func(B);
    cout<<A%C;
}