백준 13171번: A

백준 13171번: A

13171번: A

 

못풀어서 다른 사람들 블로그를 참조했다. 생각보다 엄청나게 간단한 코드였다.

이해안되는 부분이 있었는데 문제에서 잘 설명해주어서 알았다(...)

어떤 수를 x로 나눈 나머지는 더 작은 수들의 나머지를 곱한 값에서의 나머지와 같다라는 공식이 나와있고

제곱을 구하는 이진수를 구해서 비트를 뽑아내는 것도 문제에서 알려주고 있다.

나머지는 직접 구현을 해보면 되는것이다.

 

알고리즘을 풀면서 처음으로 비트 연산, 쉬프트연산을 써봤다.

직접 2진수 값을 구하는 것보다 훨씬 빠르고 편하다는 것을 알았다.

이런 류의 문제가 나오면 비트연산으로 해봐야겠다.

 

A와 X가 10^18이하의 숫자이기 때문에 long long 자료형을 사용해야한다.

 

쉬프트연산은 >>와 <<가 있는데 비트 자리를 이동하는 연산이다.

예를들어 5 >> 1 이라고 하면 5의 2진수 비트를 오른쪽으로 1만큼 이동한다는 뜻이다.

그리고 &&가 아닌 &연산은 비트 논리 연산자인데

5 & 1이라 하면은 2진수인 101과 001를 AND연산을 한다.

 

    101 == 5

&) 001 == 1

--------

    001 == 1

 

이런 연산을 통해서 코드를 구현했다.

 

#include <iostream>

using namespace std;
#define INF 1000000007
using ll = long long;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll a, x, answer = 1;
    cin >> a >> x;
    a %= INF;
    while(x != 0){
        if(x & 1) 
            answer = (answer * a) % INF;
        x >>= 1;
        a = (a * a) % INF; 
    }
    cout << answer;
    return 0;
}