백준 10854번: Divisions (C++)

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

10854번: Divisions

---

Solved By: Pollard's Rho

 

문제를 읽어보면 알겠지만 이 문제는 N이 주어지면 N의 약수의 개수를 구하는 문제입니다.

어떤 수가 주어졌을 때, 약수의 개수를 구하는 방법은 소인수분해를 하여 각 소수들의 지수에 +1을 하여 모두 곱해주면 됩니다.

소인수분해를 하기 위해서는 폴라드로 알고리즘을 사용하면 됩니다.

 

1은 인수가 없기 때문에 1 또한 약수의 개수를 구하는 코드에 돌리면 Out of Bound Error가 나기 때문에 예외 처리를 해줍니다.

#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);
    
    int T; cin >> T;
    while(T--){
    cin >> N;
    // N이 1이면 인수가 하나라서 factor의 사이즈가 1이된다.
    // 
    //if(N == 1){cout << 1; return 0;}
    factorize(N);
    sort(factors.begin(), factors.end());
    
    int expr = 2;
    int res = 1;
    for(int i = 0; i < factors.size() - 1; i++){
        if(factors[i] == factors[i + 1]){
            expr++;
        }
        else{
            res *= expr;
            expr = 2;
        }
    }
    res *= expr;
    cout << res << ' ';
    }
}