[백준 14731] 謎紛芥索紀 (Large) [C]

백준 - 14731

---

풀이

정답은 2의 K제곱들의 합이다. "백준 13731, A" 문제에서 2의 제곱을 구하는 방식을 이용해 풀이했다.

2의 K제곱(D)들의 합(sum_D)을 차수와 계수의 곱에 곱해주는 것을 반복하면 된다.

---

소스코드

#include <stdio.h>
#define MOD 1000000007
int main() {
    int N;
    scanf("%d", &N);
    long long result = 0, C, K;
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &C, &K);
        long long DC = (C*K)%MOD, sum_D = 1, D = 2;
        K--;
        while (K) {
            if (K & 1)
                sum_D = sum_D*D %MOD;
            D = D*D %MOD;
            K /= 2;
        }
        result = (result + DC*sum_D) %MOD;
    }
    printf("%lld", result);
}

---

출처 및 참고자료

14731번: 謎紛芥索紀 (Large)

[백준 13171] A [C]