정수론 관련 주요 알고리즘

정수론 관련 주요 알고리즘을 어딘가에 기록해두면 좋을 거 같아서, 코드 위주로 한번 모아봤다. (알고리즘에 대한 설명은 거의 없음)

 

1. 최대공약수 (GCD, Greatest Common Divisor)

(1) 유클리드 호제법 이용

using ll = long long;

ll get_gcd(ll a, ll b) {
    while (b != 0) {
        ll r = a % b;
        a = b;
        b = r;
    }

    return a;
}

 

• 관련 게시글 (유클리드 호제법) : https://infikei.tistory.com/46

 

2. 최소공배수 (LCM, Largest Common Multiple)

(1) 최대공약수 이용

$a \times b = \operatorname{GCD}(a, b) \times \operatorname{LCM}(a, b)$이 성립한다는 사실을 이용하여 구할 수 있다.

혹시 모를 오버플로우를 방지하기 위해 나눗셈을 먼저, 곱셈을 나중에 수행해주었다.

using ll = long long;

ll get_lcm(ll a, ll b) {
    return a / get_gcd(a, b) * b;
}

 

3. 소수 판정 (Primality Test)

(1) 기본 코드

하나의 수에 대해 소수 판정을 해야 할 때 주로 사용하는 방법이다.

using ll = long long;

bool is_prime(ll n) {
    if (n <= 1) return false;

    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

 

또는 sqrt 를 사용할 수도 있지만, 별로 추천하지는 않는다. 실수 연산은 오차가 발생할 수 있기 때문이다. 다만 sqrt(n) 를 미리 구해놓고 시작하면 반복마다 곱하기 연산 1회가 감소하게 된다는 약간의 이득은 있다.

경험상 C++에서는 sqrt 연산 결과를 즉시 정수 자료형으로 변환한다면 큰 문제는 없었다. 다른 언어나 환경에서는 실수 오차에 따라 결과가 잘못될 수 있음에 항상 유의해야 한다.

using ll = long long;

bool is_prime(ll n) {
    if (n <= 1) return false;

    ll sqrt_n = sqrt(n);

    for (ll i = 2; i <= sqrt_n; i++) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

 

(2) $\sqrt{n}$ 이하의 모든 소수들을 이용한 최적화

$\sqrt{n}$ 이하의 모든 소수들(primes)을 구해놓았다는 가정이 필요하다. (후술할 에라토스테네스의 체를 이용하여 구할 수 있음)

using ll = long long;

vector<int> primes; // 이미 구해놓았다고 가정

bool is_prime(ll n) {
    if (n <= 1) return false;

    for (int i = 0; i < size(primes) && (ll) primes[i] * primes[i] <= n; i++) {
        if (n % primes[i] == 0) {
            return false;
        }
    }

    return true;
}

 

4. 에라토스테네스의 체 (Sieve of Eratosthenes)

(1) 기본 코드

$n$ 이하의 모든 수에 대해 소수 판정을 해야 하는 경우, 에라토스테네스의 체를 이용하여 한번에 구할 수 있다.

const int MAX = 1000000;
bool sieve[MAX];

void create_sieve() {
    memset(sieve, true, sizeof sieve);

    for (int i = 2; i * i < MAX; i++) {
        if (sieve[i]) {
            for (int j = i * i; j < MAX; j += i) {
                sieve[j] = false;
            }
        }
    }
}

 

(2) $n$ 이하의 모든 소수들을 구해야 하는 경우

$n$ 이하의 모든 소수들을 primes 에 저장한다.

const int MAX = 1000000;
bool sieve[MAX];
vector<int> primes;

void create_sieve() {
    memset(sieve, true, sizeof sieve);

    for (int i = 2; i * i < MAX; i++) {
        if (sieve[i]) {
            primes.push_back(i);

            for (int j = i * i; j < MAX; j += i) {
                sieve[j] = false;
            }
        }
    }

    for (int i = primes.back() + 1; i < MAX; i++) {
        if (sieve[i]) {
            primes.push_back(i);
        }
    }
}

 

5. 소인수분해 (Prime Factorization)

(1) 기본 코드

using ll = long long;

vector<ll> get_prime_factorization(ll n) {
    vector<ll> ret;

    for (ll i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            ret.push_back(i);
            n /= i;
        }
    }

    if (n > 1) {
        ret.push_back(n);
    }

    return ret;
}

 

(2) 소인수와 지수를 함께 구하는 코드

using ll = long long;
using pll = pair<ll, ll>;

vector<pll> get_prime_factorization(ll n) {
    vector<pll> ret;

    for (ll i = 2; i * i <= n; i++) {
        ll cnt = 0;

        while (n % i == 0) {
            cnt++;
            n /= i;
        }

        if (cnt >= 1) {
            ret.emplace_back(i, cnt);
        }
    }

    if (n > 1) {
        ret.emplace_back(n, 1);
    }

    return ret;
}

 

(3) $\sqrt{n}$ 이하의 모든 소수들을 이용한 최적화

$\sqrt{n}$ 이하의 모든 소수들(primes)을 구해놓았다는 가정이 필요하다. (에라토스테네스의 체를 이용하여 구할 수 있음)

 

기본 코드 최적화

using ll = long long;

vector<int> primes; // 이미 구해놓았다고 가정

vector<ll> get_prime_factorization(ll n) {
    vector<ll> ret;

    for (int i = 0; i < size(primes) && (ll) primes[i] * primes[i] <= n; i++) {
        ll p = primes[i];

        while (n % p == 0) {
            ret.push_back(p);
            n /= p;
        }
    }

    if (n > 1) {
        ret.push_back(n);
    }

    return ret;
}

 

소인수와 지수를 함께 구하는 코드 최적화

using ll = long long;
using pll = pair<ll, ll>;

vector<int> primes; // 이미 구해놓았다고 가정

vector<pll> get_prime_factorization(ll n) {
    vector<pll> ret;

    for (int i = 0; i < size(primes) && (ll) primes[i] * primes[i] <= n; i++) {
        ll p = primes[i];
        ll cnt = 0;

        while (n % p == 0) {
            cnt++;
            n /= p;
        }

        if (cnt >= 1) {
            ret.emplace_back(p, cnt);
        }
    }

    if (n > 1) {
        ret.emplace_back(n, 1);
    }

    return ret;
}

 

6. $n!$에 곱해진 소수 $p$의 개수

(1) 기본 코드

using ll = long long;

ll count_prime_in_factorial(ll n, ll p) {
    ll cnt = 0;

    for (ll i = p; i <= n; i *= p) {
        cnt += n / i;
    }

    return cnt;
}

 

(2) 오버플로우 방지

위의 코드에서 i *= p 를 수행할 때 오버플로우가 발생할 가능성이 있다.

오버플로우 방지를 위해서 곱셈을 나눗셈으로 바꾼 버전이다.

using ll = long long;

ll count_prime_in_factorial(ll n, ll p) {
    ll cnt = 0;

    while (n > 0) {
        n /= p;
        cnt += n;
    }

    return cnt;
}

 

(3) 소수가 아니라 합성수라면?

$n!$에 곱해진 합성수 $k$의 개수를 구해야 할 수도 있다.

우선 $k$를 소인수분해해서 $k$를 이루는 모든 소인수와 그 지수를 알아내야 한다.

이렇게 알아낸 소인수와 지수를 $p_i$, $r_i$라고 하자. 그러면 $k = p_1^{r_1} \times \cdots \times p_m^{r_m}$ 라고 표현할 수 있다.

이제 각각의 $p_i$마다 $n!$에 곱해진 소수 $p_i$의 개수 $a_i$를 구하고, $\left\lfloor \frac{a_i}{r_i} \right\rfloor$ 값을 구한다.

이렇게 구한 값들 중에서 최솟값이 답이 된다.