고속 거듭제곱 알고리즘(18291번 비요뜨의 징검다리 건너기, 1629번 곱셈)

https://www.acmicpc.net/problem/18291

https://www.acmicpc.net/problem/1629

n이 4일 경우,

1001

1101

1011

1111

이렇게 4개를 생각할 수 있다.

여기에서 시작과 끝을 제외하면,

00

10

01

11

이고, 이것은 bit 연산을 생각할 수 있다.

즉, bit가 2일 때, 나올 수 있는 총 경우의 수는 2^2이고, 2^(n-2)이 답임을 알 수있다.

(예시)

000

100

010

001

011

110

101

111

비트 수 = 3, 총 개수 = 2^3

하지만 숫자가 워낙 클 경우 단순히 2^(n-2)의 작업을 할 때,  Stack Over Flow나 O(n)의 시간이 걸리게 된다.

하지만, 나머지를 적용할 수 있고, O(log n)의 알고리즘이 있다. 여기에서 n은 n, p에서의 n이 아니라 단순 시간 복잡도 표현임.

18291번 비요뜨의 징검다리 건너기

#include <bits/stdc++.h>
 
using namespace std;
 
#define Mod 1000000007
 
// a^b = a * a * ... * a(b번)
long long calculation(long long a, long long b)
{
    if (b <= 0) {
        return 1;
    }
 
    long long ret = 1;
 
    while (b)
    {
        // b의 마지막 비트와 1을 and 연산을 한다.
        if (b & 1) {
            ret *= a;
            ret %= Mod;
        }
 
        a *= a;
        a %= Mod;
        b /= 2;
    }
 
    return ret % Mod;
}
 
int main()
{
    cin.tie(0);
    int T;
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        long long n;
        scanf("%lld", &n);
        printf("%lld\n", calculation(2, n - 2));
    }
 
    return 0;
}

1629번 곱셈

#include <bits/stdc++.h>
 
using namespace std;
 
long long a, b, c;
 
// a^b = a * a * ... * a(b번)
long long calculation(long long a, long long b)
{
    long long ret = 1;
 
    while (b)
    {
        // b의 마지막 비트와 1을 and 연산을 한다.
        if (b & 1) {
            ret *= a;
            ret %= c;
        }
 
        a *= a;
        a %= c;
        b /= 2;
    }
 
    return ret % c;
}
 
int main()
{
    cin.tie(0);
    int T;
 
    scanf("%lld %lld %lld", &a, &b, &c);
    printf("%lld\n", calculation(a, b));
    
    return 0;
}