[BOJ 1629] 곱셈

https://www.acmicpc.net/problem/1629

불러오는 중입니다...

---

위 문제는 주어진 A, B, C에 대해 A^B % C를 구하는 문제이다.

 

간단하게 반복문을 B번 돌리면서 결과값에 A를 곱하고 C로 나눈 나머지를 구하면 될 거같은 문제이다.

 

바로 아래 코드처럼 말이다.

#include <stdio.h>
 
#define ull unsigned long long
 
int main() {
     int a,b,c;
 
     scanf("%d %d %d", &a,&b,&c);
 
     ull result = 1;
 
     for(int i = 0; i < b; ++i )
     {
          result = (result * a) % c;
     }
 
     printf("%d",result);
 
     return 0;
}
 

하지만 위 코드와 같이 할 수 없다.

 

왜냐하면 문제에서 주어진 값의 범위가  2,147,483,647 , 즉 정수형 범위만큼 주어지는데,

 

이만큼 반복문을 돌리면 실행시간이 시간제한을 넘어가 버린다.

 

---------------------------

 

결국 다른 방법으로 풀어야 한다.

 

실행시간을 단축시키기 위해 매번 A만큼 곱해주는 것이 아닌 

 

곱한 수를 제곱하는 방법으로 풀 것이다.

 

즉, A * A = A^2이고, A^2 * A^2 = A^4........ 이 방법을 이용해

 

A^B 꼴을 구할 것이다.

 

위 행위를 실행할 때마다 A의 지수부분은 전보다 두배가 된다.

 

예를 들어  A * A = A^2의 지수부분은 왼쪽은 1인데 오른쪽은 두배인 2가 되어있다.

 

이 방법에서 A의 지수부분은 2의 N제곱이라는 것이다.

 

이를 토대로 문제풀이방법을 구한다면

 

 

1) 

이 B를 넘지 않는 선에서 

을 구함,

 

2) 

으로 B를 다시 구하고 

이 될 때까지 1)을 반복한다.

 

3) 위 과정을 통해 나온 

을 모두 곱한 값을 C로 나눈 나머지를 구한다.

 

위 방법을 이용한 코드이다.

 

#include <stdio.h>
 
#define ull unsigned long long
 
int a, b, c;
ull PowMod(ull _a, ull _b) {
    ull i;
    for (i = 1; i << 1< _b; i = i <<1)
        _a = (_a * _a) % c;
    
    if (_b - i == 0)
        return _a % c;
    else
        return (_a * PowMod(a, _b - i))  % c;
}
 
int main() {
 
    scanf("%d %d %d", &a, &b, &c);
 
    printf("%llu", PowMod(a, b));
 
    return 0;
}