백준 1629번 곱셈

문제 링크입니다: https://www.acmicpc.net/problem/1629

시험 공부가 지긋지긋해서 푼 문제입니다.

브루트 포스로 접근하면 B의 최대값이 2억이 넘기 때문에 TLE가 발생합니다.

따라서, 분할 제곱을 이용하여 풀어야했던 문제였습니다.

#include <iostream>

using namespace std;

 

long long pow(int A, int B, int C)

{

        if (B == 1)

                 return A;

        else

        {

                 long long temp = pow(A, B / 2, C);

                 //B가 홀수면 A를 한번 더 곱해줘야한다

                 if (B % 2)

                         return ((temp*temp) % C * A) % C;

                 else

                         return (temp*temp) % C;

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int A, B, C;

        cin >> A >> B >> C;

        //A % C 전달해주는 것이 핵심

        cout << pow(A % C, B, C) << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~