[알고리즘 문제 풀기] 곱셈(1629)

1. 문제 풀이 아이디어

• 분할 정복을 이용하여 거듭 제곱을 빠르게 계산하는 방식을 사용하여 문제를 해결한다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    string[] split = sr.ReadLine().Split();
    long a = long.Parse(split[0]) % long.Parse(split[2]);
    long b = long.Parse(split[1]);
    long c = long.Parse(split[2]);
    sw.WriteLine(solve(b));

    long solve(long n)
    {
        if (n == 1)
        {
            return a;
        }
        long result = solve(n / 2);
        result = result * result % c;
        if (n % 2 == 1)
        {
            result = result * a % c;
        }
        return result;
    }
}

3. 정리

• solve(n) 함수는 분할 정복을 활용하여 a^b % c를 계산한다.

• n == 1인 경우 a를 반환한다.

• n을 절반으로 나누어 solve(n / 2)를 호출하고, 결과를 제곱하여 c로 나눈다.

• n이 홀수라면 a를 한 번 더 곱한 후 c로 나눈다.

• 최종적으로 solve(b)의 결과를 출력한다.