[C언어] 백준 1629 : 곱셈

백준 1629 : 곱셈

 

문제 링크

www.acmicpc.net/problem/1629

1629번: 곱셈

 

 

문제 내용

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

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

 

 

Idea

A, B, C는 2,147,483,647 이하의 자연수로 int 형으로 표현 가능하다.

※ int 범위 : -2^31 ~ 2^31 - 1

 

 

A를 B번 제곱을 하려면 O(n) 만큼의 시간이 걸리므로 제한 시간인 0.5를 넘게 된다. 따라서, 분할 정복을 통해 시간 복잡도를 O(log n)으로 줄여야 한다.

 

그리고 이 문제의 포인트는 함수를 돌리기 전에 A % C를 인수로 넣어줘야 한다는 점이다. (A가 C보다 작다는 조건이 없었기 때문...) 이 부분 때문에 여러 번 틀렸다...ㅠ

 

ex) B = 10 일 때,

일반적으로 n을 B만큼 제곱한다면,

func(10) = n * n * n * n * n * n * n * n * n * n

=> 총 10번 연산

 

분할 정복으로 한다면,

func(10)

= func(5) * func(5)

=> 1번

 

func(5)

= func(2) * func(2) * n

=> 2번

 

func(2)

= func(1) * func(1)

=> 1번

 

func(1) = n

=> 총 4번 연산

 

 

Code

#include <stdio.h>
 
int func(int a, int b, int c) {
    if (b > 1) {
        long long result = func(a, b / 2, c);
        if (b % 2) return ((result * result) % c * a) % c;
        else return (result * result) % c;
    }
    else return a;
}
 
int main() {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
 
    int result = func(a % c, b, c);
    printf("%d\n", result);
    return 0;
}