백준 : 1629번, 곱셈

문제 주소 : www.acmicpc.net/problem/1629

정답 비율 : 25.434% (2021.02.27 16:26 기준)

1629번: 곱셈

 

문제 요약 :

a의 b 제곱한 값을 c로 나눈 나머지를 구하시오!

 

문제 조건 :

입력 : a, b, c가 차례대로 주어집니다. (a, b, c : 1 ~ 2,147,483,647 , int 범위)

출력 : a의 b 제곱한 값을 c로 나눈 나머지를 출력

시간 : 0.5 초

 

문제 풀이 :

단순 for문을 사용하면 시간 복잡도는 O(N)입니다. 이때 N의 값이 커지면 시간 초과 발생하게 됩니다. 즉, 좀 더 효율적인 방법이 존재합니다.

 

아이디어는 다음과 같습니다. a의 n 승을 구한다고 하면 n / 2 = t라고 하면

1) n = 0 이면 1

2) n이 짝수이면 a^n = a^t * a^t

3) n이 홀수이면 a^n = a * a^t * a^t

 

이런 식으로 재귀를 구성하면 시간 복잡도는 O(logN)이 됩니다. 

 

코드는 다음과 같습니다.

 

C99

#include<stdio.h>

long long a, b, c;

long long Pow(long long n)
{
	if(n == 0LL ) return 1LL;
	else if(n % 2) return (a % c) * (Pow(n - 1) % c) % c;
	else return (Pow(n / 2) % c) * (Pow(n / 2) % c) % c;
}
int main() 
{
    scanf("%lld %lld %lld", &a, &b, &c);
    printf("%lld\n", Pow(b) % c);
    return 0;
}

 

-> a, b, c의 범위는 int형이지만 long long으로 선언한 이유는 a < c 인 상태에서 a ^ 2의 값이 int형을 넘길 수 있기 때문입니다.

 

Python3

#solve 1629

a, b, c = map(int, input().split())

print(pow(a, b, c))

-> pow 함수에서 나머지 연산을 해줍니다.