[백준 13171] A [C]

백준 - 13171

---

풀이

비트 연산자를 사용해 풀이할 수 있다.

X의 이진수를 right shift 해주면서, A를 한 번씩 제곱해주다가, X의 이진수의 가장 끝(맨 오른쪽) 숫자가 1일 때, result에 곱해주는 방식으로 풀이했다.  

 

A = 2, X = 6일 때

A	X	X & 1	result
2	110	false	1
4	11	true	4
16	1	true	64
	0

---

소스코드

#include <stdio.h>
#define MOD 1000000007
int main() {
    unsigned long long A, X, result = 1;
    scanf("%llu %llu", &A, &X);
    A %= MOD;
    while (X > 0){
        if (X & 1)
            result = (result*A) % MOD;
        X >>= 1;
        A = (A*A) % MOD;
    }
    printf("%d\n", result);
}

---

출처

13171번: A