문제 설명

• 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성
• 입력 : 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수
• 출력 : 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력

문제 해결 Key_point

• 이분 탐색예시 풀
• 모듈러 연산
• 큰 수

문제 해결 아이디어

• 일단 입력은 int의 최대 범위 안쪽임으로 Int로 입력 받음
• 모듈러 연산의 특성을 이용해 보자
  • 구해야 하는 수가 (first * second) % third 임
  • 이걸 모듈러 연산의 특성을 이용하여, 큰 수를 처리하기 좋도록 바꾸어보자
  • 그럼 ((first % third) * (second % third) % third) 가 됨
• 이제 분할 정복을 이용하여 문제를 해결해보자
  • 분할 정복 : 반반씩 나눠서 찾아보자(이 때, 정렬 되어있어야 함)
  • second를 반으로 나누어 계산하는 방식

long long mid = div_conquer(A, B / 2, C);

• 경우의 수 1 : second(mid)가 짝수일 때

if (B % 2 == 0) return (mid * mid) % C; //짝수일 때

• 경우의 수 2 : second(mid)가 홀수일 때

else return ((mid * mid) % C * A) % C; //홀수일 떄

• 이해가 잘 되지 않으므로 예제를 코드에 넣어서 그 과정을 살펴보자
  1. div_conquer(10,11,12) 호출
     1. b = 11 (홀수)
     2. mid = div_conquer(10, 5, 12)
  2. div_conquer(10, 5, 12)
     1. b = 5 (홀수)
     2. mid = div_conquer(10, 2, 12)
  3. div_conquer(10, 2, 12)
     1. b = 2 (짝수)
     2. mid = div_conquer(10, 1, 12)
  4. div_conquer(10, 1, 12)
     1. b = 1 (홀수)
     2. mid = div_conquer(10, 0, 12)
  5. div_conquer(10, 0, 12)
     1. b = 0
     2. return 1
  6. 이제 거꾸로 올라가면서 연산
  7. div_conquer(10, 1 ,12)
     1. 홀수이므로 (1 * 1) * 10 mod 12 = 10
  8. div_conquer(10, 2, 12)
     1. 짝수이므로 (10 * 10) mod 12 = 100 mod 12 = 4
  9. div_conquer(10, 5, 12)
     1. 짝수이므로 (4 * 4) * 10 mod 12 = 160 mod 12 = 4
  10. div_conquer(10, 11, 12)
      1. 홀수이므로 (4*4) * 10 mod 12 = 160 mod 12 = 4
  11. 최종 결과 : 4

소스 코드