[백준] 1629 곱셈

곱셈

문제

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

입력

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

출력

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

풀이

#include <stdio.h>

unsigned long long    recur_pow(
    unsigned long long a, unsigned long long b, unsigned long long c)
{
    unsigned long long    tmp;

    if (b == 0)
        return (1);
    else if (b % 2 == 1)
        return (a * recur_pow(a, b - 1, c) % c);
    else
    {
        tmp = recur_pow(a, b / 2, c);
        return (((tmp % c) * (tmp % c)) % c);
    }
}

int    main(void)
{
    unsigned long long    a;
    unsigned long long    b;
    unsigned long long    c;

    scanf("%d %d %d", &a, &b, &c);
    printf("%d\n", recur_pow(a, b, c));
}

반성회

처음엔 그냥 무대뽀로 a ^ b % c 했는데 그냥 터졌고 (ㅋㅋㅋㅋ)

두번째론 (((a % c) * a % c) * a % c) ..... 를 했는데 시간초과가 나왔다 b가 2147483647이면 연산을 21억번 해야하니 당연히 터질수밖에

그래서 답이없어서 찾아보니까 뭐지 이거 분할정복을 사용해야 한다고 한다 푸시스왑때 했던 그거

제곱을 하나하나 다 하기에는 너무 양이 많기 때문에 짝수개 제곱은 2개씩 묶어버리는것

unsigned long long    recur_pow(
    unsigned long long a, unsigned long long b, unsigned long long c)
{
    unsigned long long    tmp; //임시 계산값이 들어가는 곳

    if (b == 0)
        return (1); //제곱 횟수가 0이면 모든 곱이 끝나기 때문에 1을 리턴해서
    //이전 재귀 레벨에 1을 곱할 수 있도록 한다
    else if (b % 2 == 1) //제곱 횟수가 홀수라면
        return (a * recur_pow(a, b - 1, c) % c); //그냥 a를 곱한 뒤 c로 나눈 나머지 리턴
    else //제곱 횟수가 짝수라면
    {
        tmp = recur_pow(a, b / 2, c); //다음 재귀 레벨의 값을 tmp에 넣음
        //연산하다 터질 수도 있기 때문에 unsigned long long으로 선언
        //다음 재귀 레벨의 값을 이용해서 이번 재귀 레벨의 제곱연산을 해 줄 것이기 때문
        return (((tmp % c) * (tmp % c)) % c);
        //다음 재귀 레벨의 값을 c로 나눈 나머지를 제곱함으로써 제곱횟수를 1/2로 줄임
    }
}

((((a % c) * a % c) * a % c) * a % c) 를 할 거라면 모든 연산을 순서대로 하지 않고

(a % c) * a (코드에서는 tmp, 즉 이전 재귀레벨 값) 를 구한 다음에 t로 치환해서

((t % c) * (t % c)) % c 를 연산하는 방식이다

간단해보이는듯도 한데 재귀가 은근 골때려서 여러 문제를 풀어봐야 감이 잡힐듯싶다