[백준/BOJ C++] 1770번 : 배수와 약수의 개수 (정수론, 폴라드 로, Diamond IV)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1770번 : '배수와 약수의 개수' 문제의 풀이 코드와 해설을 다룹니다.

 

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

 

 

1770번 : 배수와 약수의 개수

1770번: 배수와 약수의 개수

 

단순 폴라드 로 인수분해 문제인줄 알고 접근했다가 큰 낭패를 본 문제입니다.

(https://hapby9921.tistory.com/entry/BOJ-1770-배수와-약수의-개수)에서, (저는 조건에 대해 엄밀히 증명하려다가 실패했지만) 다행히도 엄밀한 증명을 해주셨습니다. 정말 감사드립니다.

 

제가 공부하느라고 아래에 깔끔하게 한 번 더 정리하긴 했는데, 사실상 의미없고 위의 링크에서 텍스트로 정리된 수식을 이용한 증명을 보시는 편이 낫습니다.

 

 

 

핵심 아이디어는 N = p_1^x_1 = p_1^(x_1 - 1) × p_1으로 쪼갠 뒤 부등식을 만들어 부등식이 성립하지 않는 빠진 조건에 대해서만 따로 증명을 해주는 것입니다.

여기서 빠진 조건이란 p_1 = 2, x_1 = 2 즉 N = 4인 경우뿐입니다.

 

어느 한 소수라도 지수가 2 이상인 경우에는 ( i )에서 n(X) = ∞임이 증명되고, 모든 지수가 1인 경우는 ( ii )에서 증명이 되어 n(X) = k!임을 확인할 수 있습니다.

 

따라서 N을 소인수분해 했을 때 제곱수를 포함하는지에 따라 두 경우로 나누고, 제곱수를 포함하는 경우에서는 N = 4인 경우만 n(X) = 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);

    int T;
    cin >> T;
    while(T--) {
        ull N;
        cin >> N;
        if(N == 1 || N == 4) {
            cout << "1\n";
            continue;
        }

        vector<ull> List;
        while(N > 1) {
            ull div = findDiv(N);
            List.push_back(div);
            N /= div;
        }
        sort(List.begin(), List.end());

        bool isOverlap = false;
        for(int i=0; i<List.size()-1; i++)
            if(List[i] == List[i+1]) isOverlap = true;
        if(isOverlap) cout << "-1\n";
        else {
            ull ans = 1;
            for(ull i=1; i<=List.size(); i++) ans *= i;
            cout << ans << "\n";
        }
    }
}

 

증명이 어려운 문제이기 때문에 증명만 끝낸다면 코드로써의 처리는 어렵지 않습니다.

이전에 풀이했던 Diamond II 난이도의 '파리채 만들기' 문제와 비슷하게 답만 안다면 쉽게 구현이 가능합니다.

다만 큰 수에 대한 소인수분해 알고리즘인 폴라드 로 알고리즘을 사용해야하므로 폴라드 로 알고리즘에 대한 이해를 요구하는 문제입니다.

 

 

 

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

아무래도 다이아몬드4 이상의 난이도를 가진 문제들을 엄밀하게 풀려는 목적으로는 건드리지 않는 편이 나은 것 같습니다.