[수학] 백준 1629: 곱셈

1629번: 곱셈 (acmicpc.net)

1629번: 곱셈

 

그냥 (A^B)%C를 연산하면 풀 수 없다. 일단 범위를 벗어난다. 그래서 다음과 같은 modulo 연산의 성질을 이용해야 한다.

 

(X*Y)%Z = ((X%Z)*(Y%Z))%Z

 

위 성질을 통해 long long int의 범위 내에서 계속 결과값이 형성되도록 관리해 주어야 한다.

 

이를 반복문을 통해 B번 순회하면서 하고 있으면 O(N)의 시간복잡도에 걸리기 때문에 다음과 같은 지수함수의 성질을 응용한다.

 

X^Y = X^(Y/2)*X^(Y/2)

 

이를 통해 시간 복잡도를 O(logN) 수준으로 줄여야 정답 처리를 받을 수 있다.

#include <iostream>
#include <cmath>

using namespace std;

int A,B,C;
long long int calculateNominator(int a, int b)
{
    if(b==0) return 1;
    if(b==1) return a%C;
    long long int tmp = calculateNominator(a, b/2);
    if(b%2==1)
    {
        return tmp*tmp%C*a%C;
    }
    else
    {
        return tmp*tmp%C;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>A>>B>>C;

    long long int ans = calculateNominator(A,B)%C;
    cout<<ans;
}