백준 4149번: 큰 수 소인수분해 (C++)

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

4149번: 큰 수 소인수분해

---

Solved By: Pollard's Rho(Theory(Idea + Floyd's Algorithm, Birthday Paradox) + Miller-Rabin, Exponention By Squaring, Euclidean Algorithm, __int128)

 

처음으로 폴라드 로 알고리즘을 사용해보았습니다. 폴라드 로 알고리즘을 사용하기 위해 공부해야 할 사전 지식들이 꽤 많습니다.

주말에 Miller-Rabin또한 같이 정리할 것이기에 문제를 풀면서 왜 계속 '시간 초과'가 나왔는지에 대해서만 설명하겠습니다.

 

어떤 함수에서 재귀적으로 발생하는 것이 문제였는가 싶었지만 아니었습니다. unsigned long long임에도 불구하고 그들 간의 곱셈이 overflow를 발생시킬 수 있는 경우를 생각하지 못했습니다. 그래서 비표준 자료형인 __int128을 사용하여 문제를 풀 수 있었습니다.

(백준에서는 __int128을 제공합니다.)

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define ll unsigned long long
using namespace std;

ll N;
vector<ll> factors;

// Euclidean Algorithm
ll gcd(ll a, ll b){
    while(true){
        ll temp = a % b;
        a = b; b = temp;
        if(b == 0) return a;
    }
}

// Exponention By Squaring
ll power(__int128 a, __int128 b, __int128 mod){
    a %= mod;
    __int128 ret = 1;
    while(b > 0){
        if(b % 2 == 1) ret = (ret * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return (ll)ret;
}

// Miller-Rabin
bool millerRabin(ll n, ll a){
    if(a % n == 0) return true;
    ll k = n - 1;
    while(true){
        ll temp = power(a, k, n);
        if(temp == n - 1) return true;
        if(k % 2) return (temp == 1 || temp == n - 1);
        k /= 2;
    }
}

// Primality Test
bool isPrime(ll n){
    if(n == 2) return true;
    else if(n % 2 == 0) return false;
    else{
        ll base[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
        for(int i = 0; i < 12; i++){
            if(n == base[i]) return true;
            if(!millerRabin(n, base[i])) return false;
        }
        return true;
    }
}

__int128 abs128(__int128 x){
    if(x < 0) return -x;
    else return x;
}

// Pollard's Rho
void factorize(ll n){
    if(n == 1) return;
    if(n % 2 == 0){
        factors.push_back(2);
        factorize(n / 2);
        return;
    }
    if(isPrime(n)){
        factors.push_back(n);
        return;
    }
    
    __int128 x, y, c, g = n;
    
    do{
        if(g == n){
            x = y = rand() % (n - 2);
            c = rand() % 10 + 1;
            g = 1;
        }
        x = ((x * x) % n + c + n) % n;
        y = ((y * y) % n + c + n) % n;
        y = ((y * y) % n + c + n) % n;
        g = gcd(abs128(x - y), n);
    } while(g == 1);
    
    factorize(g);
    factorize(n / g);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N;
    factorize(N);
    sort(factors.begin(), factors.end());
    for(int i = 0; i < factors.size(); i++){
        cout << factors[i] << '\n';
    }
}