[BOJ] 1629. 곱셈

https://www.acmicpc.net/problem/1629

1629번: 곱셈

간단하게, A의 B제곱을 구하는 문제입니다.

B의 값이 매우 클 수 있으므로, DP를 이용합니다. A의 n제곱을 모두 저장하여 사용하기에는, 계산값을 저장하는 배열의 크기가 2,147,483,647이 될 수는 없으므로 다른 방법을 생각해봅니다.

B를 2진수로 바꾸어서, 예를 들어 29라면 11101₍₂₎를 생각해봅니다. A²⁹ = A¹⁶*A⁸*A⁴*A¹로 표현할 수 있고, 이는 다시 A²⁴*A²³*A²²*A²⁰으로 생각할 수 있습니다.

함수 func(num)은 A^2num%C를 리턴하는 함수입니다. (각 값을 구할 때마다 C로 나눈 나머지 값을 저장해서 오버플로우를 방지해줍니다.)

long long func(int num)
{

    if (visited[num])
        return d[num];
    visited[num] = true;

    if (num == 1)
        return d[1] = A % C;

    long long l = func(num - 1);
    return d[num] = l * l % C;
}

이제 B를 2의 거듭제곱들의 합으로 나누어서 각각의 곱을 구해줍니다.

long long ans(long long bb)
{
    long long v = 1;
    int deg = 1;
    while (bb > 0)
    {
        if (bb % 2 == 1)
            v = v * func(deg) % C;
        bb /= 2;
        deg++;
    }
    return v;
}

ans(bb) 함수에 B값을 넣어주면 답이 출력됩니다. 🤪