[백준] 1629번 : 곱셈 [C/C++]

#문제

1629번: 곱셈

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

1629번: 곱셈

 

---

#접근방법

일반적으로 반복문을 돌면서 곱셈과 나머지연산을 하면 약 21억번의 반복을 하므로 시간초과가 걸린다.

 

따라서 O(n)번이 아닌 O(log n)번의 시간복잡도로 풀어야 된다.

반응형

---

#풀이

#include <stdio.h>

int A,B,C;

long long int f(long long int y){
	if(y==1) return A%C;
	
	long long int k = f(y/2)%C;
	
	if(y%2==0) return k*k%C;
	else return k*k%C*A%C;
}

int main(){
	scanf("%d %d %d",&A,&B,&C);
	
	printf("%lld\n",f(B));
	
	return 0;
}

 

A를 B번 곱한 수를 C로 나눈 나머지를 구해야 한다.

 

이 문제를 풀기 위해 지수 법칙과 모듈러 성질을 알고있어야 풀 수 있다.

 

지수법칙 : a^(n+m) = a^n * a^m

모듈러 성질 : (a*b)%c = (a%c * b%c)%c

 

재귀 함수로 지수 B를 절반으로 계속 나눠서

 

k = f(y/2)

짝수일 때 : k*k

홀수일 때 : k*k*A 로 지수법칙을 사용하여 시간복잡도를 O(log n)수준으로 낮춰주었다.

 

그리고 모듈러 성질을 이용하여 long long int의 범위를 벗어나지 못하도록 해주어 정답을 구하였다.

---

#성능

---

#정리

제한시간안에 알고리즘이 돌아가도록 시간복잡도를 설계하는 것,

 

이 문제를 풀기위해 선행되어야 하는 지식

지수법칙 : a^(n+m) = a^n * a^m

모듈러 성질 : (a*b)%c = (a%c * b%c)%c 을 알고 있는 것,

 

이 법칙들을 적용시킬 수 있는 구현력을 갖추고 있으면 풀 수 있는 문제였다.