[백준 - C#] 1629번 곱셈

문제링크

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

1629번: 곱셈

 

문제

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

조건

시간제한 : 0.5초
메모리 제한 : 128 MB

입력

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

출력

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

 

문제정리

1. 자연수 A를 B번 곱한 수를 구해야합니다.
2. 곱한 수의 값이 너무 크기 때문에 C로 나눈 나머지를 구해야합니다,
3. 값이 너무 커져서 분할 정복을 이용해야합니다.

이번 문제의 경우 A를 B번 곱하는 거듭제곱 문제입니다.  간단하게 반복문을 이용하여 B번을 구하게 되면 시간 조건안에 풀이를 진행할 수 없습니다.

알고리즘의 경우 분할 정복을 이용하여 풀이를 진행하라 하여 찾아 보니 지수법칙과 모듈러의 성질을 이용하라고 하여 ㄱ오부하고 풀이 해봤습니다.

 

지수 법칙의 경우 a^(n+m) = a^n * a^m 입니다.

이것을 어떻게 이용했냐 하면 A^10 의 경우 A^5 * A^5로 나타 낼 수 있습니다.지수가 짝수인 경우는 위와 같이 표기가 되지만 홀 수 인 경우에는A^5 = A^2 * A^2 * A로 표기 할 수 있습니다. 그렇다면 이것을 이용하여 예제의 문제를 풀어보면

10^11
= 10^5 * 10^5 * 10
= (10^2 * 10^2 * 10) * (10^2 * 10^2 * 10) * 10
= (10 * 10 * 10 * 10 * 10) * (10 * 10 * 10 * 10 * 10) * 10

위와같이 표기 할 수 있으며 절반으로 나누어 사용하였기 때문에 모두 탐색할 필요 이 한번만 구하면 되고 아래 코드를 보며 한번 확인해보 실 수 있습니다.

long DaC(long a, long b)
{
    if (b == 1)
        return a;
 
    // 지수의 절반에 해당하는 값을 재귀로 풀이
    long value = DaC(a, b / 2);
 
    // 짝수일 경우
    if (b % 2 == 0)
        return value * value;
    else // 홀수 일 경우
       return (value * value) * a;
}

그럼 이제 모듈러의 성질은 왜 필요하냐고 궁금에 하실텐데,

기본적으로 지수가 짝수 일때는 c의 나머지를 그대로 사용해도 되지만,

홀 수 일 경우 long의 범위를 초과하기 때문에 문제가 생겨 모듈러의 성질을 사용해야합니다.

모듈러의 성질은 (a * b) % c = (a % c * b % c) % c 이며 홀 수 일 때 대입을 하게되면

(value *  value * a) % c 
= ((temp * temp % C) * (A % C)) % C
= ((temp * temp % C) * A) % C

위와 같이 사용할 수 있습니다.

 

이번 문제를 풀며 지수법칙과 모듈러의 성질을 공부할 수 있는 좋은 시간이였습니다.

 

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    long[] input = Array.ConvertAll(reader.ReadLine().Split(), long.Parse);
    long a = input[0];
    long b = input[1];
    long c = input[2];
 
    //지수법칙 : a^(n+m) = a^n * a^m
    //모듈러 성질 : (a * b) % c = (a % c * b % c) % c
    writer.WriteLine(DaC(a, b));
 
    reader.Close();
    writer.Close();
 
    // DivideAndConquer 분할 정복
    long DaC(long a, long b)
    {
        if (b == 1)
            return a % c;
 
        // 지수의 절반에 해당하는 값을 재귀로 풀이
        long value = DaC(a, b / 2);
 
        // 짝수일 경우
        if (b % 2 == 0)
            return value * value % c;
        else // 홀수 일 경우
            return (value * value % c) * a % c;
    }
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.