[백준/BOJ C++] 13926번 : gcd(n, k) = 1 (폴라드 로 알고리즘, 서로소 개수 공식, Diamond V)

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

 

문제 난이도는 Solved.ac 기준 Diamond V에 해당하며, 문제를 풀이하기 위해 밀러-라빈 소수 판정법 알고리즘, 폴라드 로 인수분해 알고리즘, 그리고 서로소의 개수를 구하는 공식에 대한 이해가 필요합니다. (굳이 필요는 없지만 더 나아가서는 오일러 Phi 함수에 대한 배경지식도 있으면 좋음)

 

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

↑ 문제를 풀이하기 위한 알고리즘에 대한 배경 지식이 부족하다면 비슷한 종류의 문제 풀이로써 위의 문제를 참고하면 좋을 것 같습니다.

 

 

13926번 : gcd(n, k) = 1

13926번: gcd(n, k) = 1

 

자연수 n이 주어졌을 때 gcd(n, k) = 1을 만족하는 1~n 사이의 k의 개수, 즉 n 이하의 n과의 서로소의 개수를 구하는 짧은 문제입니다.

다만 n의 입력 범위가 10^18 이하이기 때문에 제한 시간 안에 처리하기 쉽지 않아 보이는 문제입니다.

 

 

 

먼저 문제의 목적인 '서로소의 개수'를 구하는 방법에 대해 생각해봅시다.

오일러 피(Phi) 함수에 대해 알고 있으면 좋으나, 서로소의 개수를 구하기만 하는데에는 거기까지는 필요 없습니다.

오일러 피 함수에 대한 이해를 바탕으로 공식만 뽑아오면, N을 소인수분해 한 뒤 각 소인수의 지수와는 관계없이 (어차피 p^2 역시 p를 약수로 가지므로 상관없이 지워짐), 서로소의 개수는 각 소인수에 대해 p-1/p만큼씩으로 감소합니다.

 

따라서 위의 공식을 활용하기 위해서는 소인수분해가 선행되어 있어야 함을 알 수 있습니다.

10^18과 같은 큰 수를 짧은 시간에 소인수분해 하기 위해서는 폴라드 로 알고리즘을 활용하는 것이 가장 최선입니다.

폴라드 로 알고리즘을 활용하는 문제는 포스트 위에 첨부해두었기 때문에, 여기서는 설명을 생략하고 활용하도록 하겠습니다.

 

 

#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, temp;
    cin >> N; temp = N;
    if(N == 1) { cout << "1"; return 0; }

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

    ull Ans = temp;
    Ans = Ans/List[0]*(List[0]-1);
    for(int i=1; i<List.size(); i++)
        if(List[i] != List[i-1]) Ans = Ans/List[i]*(List[i]-1);
    cout << Ans;
}

 

위의 설명을 바탕으로 코드를 구현하면 위와 같습니다.

폴라드 로 알고리즘과 그 과정에서 사용되는 밀러-라빈 소수판별법은 이전 포스트와 내용이 중복되므로 설명을 생략하도록 합니다.

중요한 부분은 소인수의 개수 공식을 구현하는 부분인데, List에 소인수들을 저장한 뒤 중복되는 부분은 처리되지 않고 소인수가 바뀌는 부분에서만 p-1/p를 곱해 답을 구할 수 있도록 구현하였습니다.

 

추가로 n이 1인 경우에는 소인수가 하나도 나오지 않으므로 예외 처리를 따로 해주어 사전에 종료되도록 설정하는 것이 좋습니다.

 

 

 

풀이를 제출해보면 위의 코드를 기준으로 20ms의 시간을 기록하고 정답 처리를 받을 수 있습니다.