https://www.acmicpc.net/problem/1629 큰 수의 곱셈 문제가 있을 때 떠올리면 좋은 건 분할정복과 비트마스킹이다.a를 b번 곱할 때 반복문으로 b번 곱하는 것이 아니라, 지수를 반으로 나눠서 거듭제곱하는 방식이다. 물론 이때 지수가 짝수이면 그냥 반 갈라도 되지만 지수가 홀수이면 1을 하나 빼서 나눈 뒤 마지막에 한번 더 곱해줘야 한다.처음에는 그냥 비트마스킹만 생각했는데 그럼 2의 거듭제곱만으로 계산해야 하니 귀찮았다.. 단 숫자가 아주 커질 수 있기 때문에 그냥 계산하면 오류가 날 수 있으므로 계산 과정에서 매번 c로 나눈 나머지를 사용하도록 해서 오버플로가 나지 않게 해준다. b & 1 이라는건 비트마스킹에서 첫번째 비트가 1인 수와 and를 했을 때 true 즉 0이 ..
