[BOJ 1629] 곱셈 (C++)
곱셈 (Silver 1) 문제 전체 문제 보기 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 접근법 이 문제는 A를 B번 곱한 값을 C로 나머지를 구하는 문제이다. 그런데 B느 최대 2,147,483,647로 굉장히 크다는 것이 문제이다. Brute force 방식으로 A를 B회 곱하기에는 B가 너무 크다. Brute force보다 더 나은 방식을 찾아야 한다. 나머지 연산은 \((a \bmod\ c * b \bmod\ c)\bmod\ c = (a * b) \bmod\ c \)와 같이 연산 중간중간에 나머지 연산을 한 결과와 전체 결과에 나머지를 구한 결과가 같다. 우리는..
