[백준/BOJ C++] 10854번 : Divisions (폴라드 로 알고리즘, Diamond V)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 10854번 : 'Divisions' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Diamond V에 해당하며, 문제를 풀이하기 위해 밀러-라빈 소수 판정법 알고리즘과 폴라드 로 인수분해 알고리즘에 대한 이해가 필요합니다.

 

배경 지식이 필요한 분들을 위해 아래에 각 알고리즘에 대한 설명을 다루고 있는 링크를 첨부해두겠습니다.

 

[C++ 알고리즘] 밀러-라빈 소수 판별법 (Miller-Rabin Primality Test)

↑ 밀러-라빈 소수 판별법 알고리즘에 대한 설명은 위의 링크에 정리되어 있습니다.

 

[C++ 알고리즘] 폴라드 로 알고리즘 (Pollard's rho algorithm, 큰 수 소인수분해 알고리즘)

↑ 폴라드 로 인수분해 알고리즘에 대한 설명은 위의 링크에 정리되어 있습니다.

 

 

10854번 : Divisions

10854번: Divisions

 

입력된 10^18 이하의 자연수에 대해 약수의 개수를 출력하는 문제입니다.

어떤 수의 약수의 개수를 구하는 것은 중학교 수학 과정에서 배웁니다.

자연수를 소인수분해 한 뒤, 각 소수의 지수 + 1씩을 각각 곱해주면 약수의 개수가 됩니다.

예를 들어 18이라는 자연수의 약수를 구한다고 할 때, 18을 소인수분해 해주면 2^1 × 3^2이므로, (1+1)×(2+1) = 6이 18의 약수의 개수가 됩니다.

이것은 왜냐하면 어떤 소인수의 개수를 a라고 하면 0~a 사이의 지수를 선택하여 약수를 만들 수 있고 이 때 선택지는 총 a+1개가 되며, 이 과정을 각각의 소인수에 대해 수행할 수 있기 때문입니다.

 

어쨌든 문제를 풀이하기 위해서는 수를 소인수분해하고, 각 지수의 개수 + 1을 곱한 값을 답으로 얻어주면 됨을 알 수 있습니다.

 

 

#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;

ull Power(__int128 x, __int128 y, __int128 mod) { // ret = (x^y)%mod
    x %= mod;
    __int128 ret = 1;
    while(y > 0) {
        if(y%2 == 1) ret = (ret*x)%mod;
        x = (x*x)%mod;
        y /= 2;
    }
    return (ull)ret;
}

bool checkPrime(ull n, ull a) {
    if(a%n == 0) return true;
    ull k = n-1;
    while(1) {
        ull temp = Power(a, k, n);
        if(temp == n-1) return true;
        if(k%2 == 1) return (temp == 1 || temp == n-1);
        k /= 2;
    }
}

bool isPrime(ull n) {
    if(n == 2 || n == 3) return true;
    if(n%2 == 0) return false;

    ull a[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for(int i=0; i<12; i++)
        if(!checkPrime(n, a[i])) {
            return false;
            break;
        }
    return true;
}

ull GCD(ull a, ull b) {
    if(a < b) swap(a, b);
    while(b != 0) {
        ull r = a%b;
        a = b;
        b = r;
    }
    return a;
}

ull findDiv(__int128 n) {
    if(n%2 == 0) return 2;
    if(isPrime(n)) return n;

    __int128 x = rand()%(n-2) + 2, y = x, c = rand()%10 + 1, g = 1;
    while(g == 1) {
        x = (x*x%n + c)%n;
        y = (y*y%n + c)%n;
        y = (y*y%n + c)%n;
        g = GCD(abs(x-y), n);
        if(g == n) return findDiv(n);
    }
    if(isPrime(g)) return g;
    else return findDiv(g);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    ull N;
    cin >> N;
    if(N == 1) { cout << "1"; return 0; }

    vector<ull> ansList;
    while(N > 1) {
        ull div = findDiv(N);
        ansList.push_back(div);
        N /= div;
    }

    sort(ansList.begin(), ansList.end());
    ull ans = 1, mulNum = 2;
    for(int i=0; i<ansList.size()-1; i++) {
        if(ansList[i] == ansList[i+1]) mulNum++;
        else ans *= mulNum, mulNum = 2;
    }
    ans *= mulNum;
    cout << ans;
}

 

이를 구현하기 위해 (밀러-라빈 소수판별법이 사용된) 폴라드 로 알고리즘을 사용해주고, 여기에서 구한 소인수들을 벡터에 저장 및 정렬해준 뒤, 중복되는 소인수들의 개수를 count하여 위에서 구한 약수의 수 식에 대입해주면 됩니다.

 

주의할 점은, 1을 예외 처리하지 않으면 ansList에 1개의 값만 들어가기 때문에 outOfBounds 에러가 발생하게 됩니다.

따라서 1이 입력으로 들어오는 경우에는 바로 처리하고 종료해주도록 합시다.

 

 

 

제출해보면 위와 같이 정답 처리를 받을 수 있습니다.