|C++| sw 7965 - 퀴즈(빠른 제곱)

0. [c++] sw 7965 - 퀴즈

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWuSh2IKmu0DFASy&categoryId=AWuSh2IKmu0DFASy&categoryType=CODE

1. 풀이

이 문제를 해결하기 위해서는 빠르게 연산하는 pow를 만들어야 되겠다는 생각이 들었다.

pow 연산을 빠르게 하기 위해서 2진수의 비트마스크 방식을 활용하였다.

소스코드 부분에 구현해놓은 pow()부분을 참고하면, if(exp&1)이란 부분을 확인 할 수 있는데, 이 부분은 2진수로 exp를 바꾸었을 때, 현재 부분이 1이라면 a를 곱해주라는 얘기이다.

예시로 하나를 보여주면,

5^5를 해보자.

우선 exp = 5가 되고, 이를 이진수로 표현하면 101이 된다.

1) while(exp){}에 들어가면, 첫 if문 (exp & 1 )은 (10'1' & 1) 로 1이 일치하므로, ret = 1 * 5 = 5가 된다.

2) exp >>= 1에서 101은 한 비트 밀려서 10이 된다.

3) factor *= factor에서  factor = 5*5 = 25가 된다.

4) if문에서 1'0'은 1과 일치하지 않으므로 ret은 변화하지 않는다.

5) factor *= factor 에서 factor = 25*25 = 625가 된다.

6) if문에서 '1'은 1과 일치하므로 ret *= factor,  ret = 5*625 = 3125가 된다.

이제 exp는 0이므로 반복은 끝나고, 우리가 구한 5^5는 3125로 원하는 수를 구하게 되었다.

뭐, 이런식으로 구동하는 pow를 구현하였고, 이를 바탕으로 코드가 시작하면 미리 전처리를 하고, 원하는 N을 넣었을 때, 필요한 부분의 cache를 불러와 출력하는 형태의 코드를 만들어주었다.

2. 소스코드

#include<iostream>
 
using namespace std;
 
typedef unsigned long long ull;
const int INF = 1000000007;
 
int cache[1000001];
 
int pow(const int& k) {
    ull ret = 1;
    ull factor = k;
    int exp = k;
    while (exp) {
        if(exp & 1) {
            ret *= factor;
        }
        exp >>= 1;
        factor *= factor;
        factor %= INF;
        ret %= INF;
    }
    return ret;
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T, N;
    cin >> T;
    cache[1] = 1;
    for (int i = 2; i <= 1000000; i++) {
        cache[i] = (cache[i - 1] + pow(i)) % INF;
    }
    for (int i = 0; i < T; i++) {
        cin >> N;
        cout << "#" << i + 1 << " " << cache[N] << "\n";
    }
 
 
    return 0;
}

3. 참고

빠른 pow 구현하기

https://techlog.gurucat.net/323

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!