티스토리 뷰

알고리즘 관련/BOJ

BOJ)1629 곱셈

JASON 자손9319 2017. 3. 5. 15:28

문제:icpc.me/1629


A^B(MOD C)를 구하는 문제이다. A,B,C가 2^31까지 들어오므로 단순 구현으로는 오버플로우나 시간초과를 받게 될 것이다.


하지만 우리는 분할정복을 이용하여 logB 시간에 A^B를 구해줄 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a, b, c;
ll power(ll x, ll y) {
    ll ret = 1;
    while (y > 0) {
        if (y % 2) {
            ret *= x;
            ret %= c;
        }
        x *= x;
        x %= c;
        y /= 2;
    }
    return ret;
}
int main() {
    scanf("%lld%lld%lld"&a, &b, &c);
    printf("%lld\n", power(a%c, b));
    return 0;
}
cs



'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1252 이진수 덧셈  (0) 2017.03.07
BOJ)2636 치즈  (0) 2017.03.06
BOJ)1629 곱셈  (0) 2017.03.05
BOJ)1201 NMK  (0) 2017.03.05
BOJ)12026 BOJ 거리  (0) 2017.03.01
BOJ)10816 숫자 카드2  (1) 2017.03.01
댓글
댓글쓰기 폼