[백준 1629] 곱셈

www.acmicpc.net/problem/1629

1629번: 곱셈

모듈러 연산과 제곱 빠르게 하기 응용버전이다.

제곱빠르게 하기는 재귀로도 풀 수 있기 때문에 이전에 풀었던 관련 문제를 참고한다.

 

이전 포스팅 참고

eazymean.tistory.com/192?category=883575

리트코드에서 동일한 문제를 푼 경험이 있다. 

 

모듈러 연산에 대해서 짚고 넘어가자면

 (a*b) mod n = ((a mod n) * (b mod n)) mod n이다.

 

문제에서 주어진 a,b,c의 범위가 상당히 크므로 long long으로 선언해도 오버플로우가 발생하기 쉽다.

따라서 result와 a에 대해 mod 연산을 계속 해야한다. 

#include <stdio.h>

using namespace std;
long long a, b, c;
int main(void)
{
  scanf("%lld %lld %lld", &a, &b, &c);

  long long result = 1;

  if (b > 1)
  {
    while (b > 0)
    {
      a %= c;
      if (b & 1)
      {
        result *= a;
        result %= c;
      }
      a *= a;
      b = b >> 1;
    }
    result %= c;
  }
  else
  {
    result = a % c;
  }

  printf("%lld\n", result);

  return 0;
}