백준 13926번: gcd(n, k) = 1 (C++)

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

13926번: gcd(n, k) = 1

---

Solved By: Pollard's Rho, Euler Phi Function

 

내 생각

Pollard's rho를 이용해 소인수 분해한 factor들을 구하고, 중복되는 것들은 없애서 1 ~ N까지의 수들을 탐색하며 factor로 나머지가 0으로 나뉘는 것이 있는지 탐색한다.

==> 시간 초과

N이 (1 <= N <= 10^18)일 뿐인 더러 factor의 개수가 X라 했을 때, Time Complexity가 O(NX)로 엄청나게 큰 복잡도를 가지게 된다.

 

Euler Phi Function

이럴 때 사용할 수 있는 함수가 있다. 바로 Euler Phi Function으로 양의 정수 M이 주어졌을 때, M의 소인수들을 알고 있다면 공식을 사용하여 M 이하의 양의 정수 중 M과 서로소인 수의 개수를 구한다.

 

[공식]

주어진 수: n, n의 소인수: p

출처: 위키백과

gcd(n, k) = 1인 n과 k가 서로소라는 뜻이므로 Euler Phi Function을 적용할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
#define ull unsigned long long
#define i128 __int128
using namespace std;

ull N;
vector<ull> factors;

ull power(i128 a, i128 b, i128 mod){
    a %= mod;
    __int128 ret = 1;
    while(b > 0){
        if(b % 2 == 1) ret = (ret * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return (ull)ret;
}

bool millerRabin(ull n, ull a){
    if(a % n == 0) return true;
    ull k = n - 1;
    while(true){
        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) return true;
    else if(n % 2 == 0) return false;
    else{
        ull base[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
        for(auto a : base){
            if(n == a) return true;
            if(!millerRabin(n, a)) return false;
        }
        return true;
    }
}

i128 gcd(i128 a, i128 b){
    while(true){
        i128 temp = a % b;
        a = b;
        b = temp;
        if(b == 0) return a;
    }
}

i128 f(i128 x, i128 c, i128 mod){
    return ((x * x) % mod + c) % mod;
}

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

void factorize(ull 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;
    }
    
    i128 x, y, c, g = n;
    do{
        if(g == n){
            x = y = rand() % (n - 2) + 2;
            c = rand() % 10 + 1;
        }
        x = f(x, c, n);
        y = f(f(y, c, n), c, 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;
    ull ans = N;
    if(N == 1){
        cout << 1;
        return 0;
    }
    factorize(N);
    sort(factors.begin(), factors.end());
    factors.erase(unique(factors.begin(), factors.end()), factors.end());
    // Euler Phi Function
    for(auto v : factors){
        ans = ans / v * (v - 1);
    }
    cout << ans;
    return 0;
}