빠른 거듭제곱

비트 시프트를 사용한 거듭제곱은 O(1)의 시간 복잡도를 가지지만 최대 63 제곱까지만 가능합니다. 반면, 빠른 거듭제곱 알고리즘은 O(log n)의 시간 볔잡도를 가지며 10^9 제곱까지 지원합니다. 모듈러 연산은 곱셈 단계에서 수행해야 합니다.

이 방법은 a^k mod p를 계산하는 데 사용되며, a, k, p는 각각 1e9까지 가능합니다. 이를 통해 O(log k)의 시간 복잡도로 효율적인 계산이 가능합니다.

int fastPower(int base, int exp, int mod) {
    int result = 1;
    while (exp > 0) {
        if (exp & 1) result = ((long long)result * base) % mod;
        base = ((long long)base * base) % mod;
        exp >>= 1;
    }
    return result;
}

오일러 정리 적용

오일러 함수를 이용하여 매우 큰 지수에 대해 모듈로 연산을 수행할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

long long fastPower(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

long long eulerTotient(long long n) {
    long long result = n;
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            result -= result / i;
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

모듈로 역원 구하기

소수 모듈로 아래에서만 유효하며, gcd(a, b) = 1인 경우 a와 b가 서로소임을 의미합니다.

int inverseMod(int a, int p) {
    return fastPower(a, p - 2, p);
}

빠른 행렬 거듭제곱

다항식 재귀 관계를 계산하는 데 사용됩니다.

void matrixMultiply(int c[], int a[], int b[][3], int mod) {
    int temp[3] = {0};
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            temp[i] = (temp[i] + (long long)a[j] * b[j][i]) % mod;
    memcpy(c, temp, sizeof(temp));
}

void matrixPower(int res[][3], int mat[][3], int n, int mod) {
    int temp[3][3];
    memset(temp, 0, sizeof(temp));
    for (int i = 0; i < 3; ++i) temp[i][i] = 1;
    while (n > 0) {
        if (n & 1) matrixMultiply(res, res, mat, mod);
        matrixMultiply(mat, mat, mat, mod);
        n >>= 1;
    }
}

위치값 및 비트 연산

최하위 비트를 얻기 위한 lowbit 함수입니다.

int lowbit(int x) {
    return x & -x;
}

소수 판별 및 분해

소수 판별과 소인수 분해 알고리즘입니다.

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; ++i)
        if (n % i == 0) return false;
    return true;
}

void primeFactorize(int n) {
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            int count = 0;
            while (n % i == 0) n /= i, ++count;
            cout << i << " " << count << endl;
        }
    }
    if (n > 1) cout << n << " " << 1 << endl;
}