[BOJ 4149] 큰 수 소인수분해

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

 

큰 수를 소인수분해 해보자.

 

우선 밀러-라빈 알고리즘으로 해당 숫자가 소수인지 판별한 후 폴라드-로 알고리즘으로 소인수분해 하면 된다.

밀러-라빈 알고리즘은 검사하는 소수의 개수를 $k$, 소인수분해 하려는 수를 $n$이라 할 때 시간복잡도가 $O(k \log^3 {n})$이다. 자세한 사항은 위키백과를 참고하자.

 

참고로 $2^{64}$까지의 숫자를 결정론적으로 검사할 때는 $p = 2, 3, 5, ..., 37$이면 충분하다.

 

폴라드-로 알고리즘은 어떤 난수 발생 함수(이를테면 $f(x)=(x^2+1)\mod n$)가 $\mod n$에 대해 반복됨을 이용하는 것인데, 그 반복되는 주기가 $n$의 약수임을 이용한다. 자세한 내용은 나도 잘 모른다.. 아무튼 시간복잡도가 가장 작은 소인수의 루트에 해당된다고 알려져 있다. 즉 합성수인 $n$에 대해 최악의 경우 $O(n^{1/4})$에 작동한다는 것인데, 해당 문제에서 $n$의 범위가 대략 $10^{18}$정도 되기 때문에 이 문제를 풀 수 있다. 참고로 폴라드-로 알고리즘도 밀러-라빈 알고리즘과 비슷하게 실패할 수도 있기 때문에 인수를 찾을때까지 함수를 랜덤하게 바꿔 반복해준다. (그렇게들 하더라.)

 

코드

#include <bits/stdc++.h>
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 101010;
const int INF = 1e9;
const ll LINF = 9e18;

ll mymul(ll a, ll b, ll mod) {
    ll ret = 0;
    while(b > 0) {
        if(b & 1) ret = (ret + a) % mod;
        b >>= 1;
        a = (a * 2) % mod;
    }
    return ret;
}

ll mypow(ll a, ll b, ll mod) {
    ll ret = 1;
    while(b > 0) {
        if(b & 1) ret = mymul(a, ret, mod);
        b >>= 1;
        a = mymul(a, a, mod);
    }
    return ret;
}

bool miller_rabin(ll n) {
    vector <ll> p = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

    int s = 0; ll d = n - 1;
    while(d % 2 == 0) d /= 2, s++;
    for(auto a : p) {
        if(a == n) return true;
        if(a > n) break;
        bool flag = false;
        for(int i = 0; i < s; i++) {
            if(mypow(a, (1 << i) * d, n) == n - 1) flag = true;
        }
        if(!flag && mypow(a, d, n) != 1) return false;
    }
    return true;
}

ll gcd(ll x, ll y) {
    if(!y) return x;
    return gcd(y, x % y);
}

vector <ll> ans;

void factorize(ll n) {
    if(n == 1) return;
    if(n % 2 == 0) {
        ans.eb(2);
        factorize(n / 2);
        return;
    }
    if(miller_rabin(n)) {
        ans.eb(n);
        return;
    }

    ll a, b, c, g = n;
    auto f = [&](ll x) {
        return (c + mymul(x, x, n)) % n;
    };
    do {
        if(g == n) {
            a = b = rand() % (n - 2) + 2;
            c = rand() % 20 + 1;
        }
        a = f(a);
        b = f(f(b));
        g = gcd(abs(a - b), n);
    } while(g == 1);
    factorize(n / g), factorize(g);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    ll n;
    cin >> n;
    factorize(n);
    sort(all(ans));

    for(auto i : ans) cout << i << '\n';
}