[Algorithm] 백준 - 11689번 GCD(n, k) = 1

문제 소개

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

 

풀이 과정

자연수의 범위가 10^12이다. 절대로 1부터 순회해서 서로소를 구할 수 없다. 물론 소수를 구하게 된다면 좀 더 수월해지겠지만 순회하는 방식으로는 도저히 구할 수가 없다는 것을 알게 되었고, 결국 오일러의 피 함수를 찾아보게 되었다. 소인수를 통해 서로소의 개수를 구할 수 있는 함수이다.

 

오일러 피 함수 - 위키백과, 우리 모두의 백과사전

 

공식을 알고나니 구현하기는 너무 쉬웠다. 주의해야 할 사항은 root를 기준으로 반복문을 돌려줬는데 n보다 작고 root보다 큰 소인수는 하나 존재할 수 있다. 두 개 이상 존재하면 무조건 n보다 커지기 때문에... 그래서 마지막에 n이 1이 되지 않는다면 서로소라고 생각하고 오일러 곱 공식을 한번 더 적용한다.

import Foundation

// 에라토스테네스의 체
var n = Int(readLine()!)!
let root = Int(sqrt(Double(n)) + 1)

var isPrime = Array(repeating: true, count: root + 1)
guard n > 1 else {
    print(1)
    exit(0)
}

for i in 2...root {
    guard isPrime[i] else { continue }
    var k = i * i
    while k <= root {
        isPrime[k] = false
        k += i
    }
}

// 오일러 피함수
var phi = n
for p in 2...root {
    guard isPrime[p] else { continue }
    if n % p == 0 {
        phi = phi / p * (p - 1)
    }
    while n % p == 0 {
        n /= p
    }
}

print(n == 1 ? phi : phi / n * (n-1))

 

성능은 아주 좋은 듯 하다.