[백준] 1629번 : 곱셈 (#모듈러연산, 분할정복, 재귀, overflow)
https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 무작정 풀면서 들이박는? 중인 나한테는 풀이를 보고도 한번에 이해하기 힘든 문제였다... 풀기 전에 모듈러 연산과 분할정복에 대해 알아야 한다. 모듈러 연산 (a+b)%c = (a%c + b%c)%c (a*b)%c = (a%c * b%c)%c 분할정복 (Divide and Conquer) b가 짝수일때 : a^b = a^(b/2) x a^(b/2) b가 홀수일때 : a^b = a^(b/2) x a^(b/2 + 1) 첫번째, 1629번 문제의 입력값 A,B,C 는..
2024. 1. 17.