백준 7806 GCD!

문제

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

 

풀이

1. GCD를 구하는 것은 유클리드 호제법으로 log 복잡도로 구할 수 있으나, 저 거대한 팩토리얼을 다룰 도리는 안보인다.

다른 방법(정확히는 더 고전적인 방법)으로 GCD를 구할 수 있다.

N의 소인수의 집합을 A, M의 소인수의 집합을 B라고 하자.

I = A ∩ B, e ∈ I 라고 하자 (사실 A 또는 B 둘중 하나에 대해서 수행해도 된다.)

cnt(num,x)는 소인수 x가 num에 몇개 포함돼있는지(num을 x로 몇번 나누어 떨어지게 나눌 수 있는지) 리턴하는 함수라 하자.

# python
GCD = 1
for e in I:
    for i in range(min(cnt(N,e),cnt(M,e))):
        GCD = GCD * e

이 방식으로 GCD를 구할 수 있고 복잡도는 소인수 분해를 수행하는 O(sqrt(N) + sqrt(M))이다. 

 

2. K의 최대는 10^9이므로 sqrt(K) 복잡도로 소인수분해가 가능하다.

1번의 코드를 볼때, K를 소인수분해 한 뒤 각각의 소인수로 최대한 N!을 나눠주면 GCD를 구할 수 있다.

# python
GCD = 1
# fac: 소인수 분해 결과를 key:value 꼴로 나타낸 dict 
# key:소인수, value: 소인수갯수
for e in fac:
  # 결론적으로 이 부분은 min(cnt(N!,f),cnt(K,f)) 를 나타낸다.
    for i in range(fac[f]):
        if not canDiv(N!):
            break
        GCD = GCD * e

 

3. 이제 우리가 구현해야할 것은 N!을 나눌 수 있는 조건(canDiv(N!))을 찾는 것과, fac을 구하는 것이다. 소인수 분해 결과인 fac을 구하는 방법은 sqrt 복잡도로 각자 편한대로 구현하면 된다.

 

4. factorial은 1*2*3*...*N꼴이고, 1~N에는 x,2x,3x,...tx (tx <= N)이 포함돼 있을 것이다.

어떤 소인수 x에 대해, N!은 최소 t번 x로 나눌 수 있다. t번보다 더 못나눌까?

x^2,2x^2,3x^2,...sx^2(sx^2<=N)이 남아있을 것이다. s번 더 t로 나눌 수 있다. s + t번보다 더 못나눌까?

x^3,x^4,...x^y (x^y<=N)의 배수도 남아있을 것이고 x^y까지 처리하면 완전히 x로 나눌 수 있다.

 

5. ax <= N을 만족하는 a의 최댓값을 찾는 법은 N // a (또는 int(N/a))로 찾을 수 있다.

x^1부터 x^y까지 진행하는 것은 최대 log(N)번 진행한다.

for f in fac:
    x = 1
    count = 0 // N!을 f로 몇번 나눌 수 있는가
    for i in range(1,111):
        x = x * f
        if x > N:
            break;
        count += n // x

따라서 이 코드는 적절한 시간복잡도O(sqrt(K)*log(N))에 동작한다.

우린 이 코드로 cnt(N!,f)를 구할 수 있다. cnt(K,f)는 fac[f]로 구할 수 있다.

 

6. 최종 코드

GCD = 1
for e in I:
    for i in range(min(cnt(N,e),cnt(M,e))):
        GCD = GCD * e
######
GCD = 1
for f in fac:
    for i in range(min(cnt(N!,f),fac[f])):
        GCD = GCD * e
#####
GCD = 1
for f in fac:
    x = 1
    count = 0
    for i in range(111):
        x = x * f
        if x > N:
            break;
        count += N // x
    for i in range(min(count,fac[f])):
       GCD = GCD * e
print(GCD)