[1629] 곱셈 - 재귀/수학 ★★☆☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/1629

1629번: 곱셈

---

[ 문제 접근 ]

 

 

재귀를 이용하여 분할정복을 통해 풀어야하는 문제.

 

 

[ 나머지 정리 ]  참고할 만한 내용.

참고 : https://blog.naver.com/wusonjae/221444777681

참고 : https://johngrib.github.io/wiki/discrete-math-modular/

참고 :: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=dgsw102&logNo=221234184168 

 

 

---

[ 최종 코드 ]

 

#include<iostream>
#include<vector>
#include<math.h>

using std::cin; using std::cout;
using std::vector;

int a, b, c;

int solve(int a, int b) {
	if (b <= 1) {
		return  a % c;
	}
	long long r = solve(a, b / 2);
	if (b % 2 == 0) {
		return r * r % c;
	}
	else {
		return (((r * r) % c)*(a%c)) % c;
	}

}


int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> a >> b >> c;


	cout << solve(a, b);



	return 0;
}

---

[ Key Point ]

 

👉 recursion 으로 풀어야겠다를 생각 했어야 하고, base case 와 점화식을 도출 할 줄 알아야한다.

 

---