백준 1629번 - 곱셈

백준 1629번 - 곱셈

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

문제

• 자연수 A를 B번 곱한 수를 알고 싶다.

• 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다.

• A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

• 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

접근

• a를 b번 곱하는 방법으로 계산하면 시간 초과가 뜬다.

• ​ 임을 이용하여 곱연산을 최소화 한다.

• ret 값을 1로 초기화 한 다음, b를 2로 나누었을 때 나머지가 1인 경우에만 ret값에다가 a를 곱해준다.

• a에는 a의 제곱을 대입한다.

ret     a       b       b%2
-----------------------------
1       3       13      1
3       9       6       0
3       81      3       1
243     6561    1       1
1594323

• 위의 방법론에서 오버플로우가 발생하지 않도록 곱연산이 진행될 때마다 모듈러 연산을 해준다.

C++ Code

#include <cstdio>
using namespace std;
​
long long a, b, c;
​
long long power(long long a, long long b, long long c) {
    long long ret = 1LL;
    while (b > 0) {
        if (b % 2 == 1) {
            ret *= a;
            ret %= c;
        }
        a *= (a%c);
        a %= c;
        b /= 2;
    }
    return ret % c;
}
​
int main() {
​
    scanf("%lld %lld %lld", &a, &b, &c);
    printf("%lld\n", power(a, b, c));
    
    return 0;
}