[백준 | Python] #9363 - 큰 나눗셈

9363번: 큰 나눗셈

문제

두 수 $A$, $B$의 인수들 $A_1, A_2, ..., A_n$과 $B_1, B_2, ..., B_n$이 주어진다. 주어진 인수를 통해 $\frac{A}{B}$를 기약분수 형태로 나타내어 출력하여라.

아이디어

각 인수의 최댓값은 100만이다. 100만까지의 소수를 미리 구해놓는 것이 좋을 것 같다. (총 78498개)

 

인수들의 개수는 최대 22만개이다. 단순히 이들을 모두 곱한다면 당연히 연산 가능한 수를 벗어나므로 인수들을 모두 소인수분해하여 두 수의 소인수의 개수를 각각 세서 A와 B의 소인수 리스트에 저장하는 것이 좋을 것 같다.

 

100만까지의 수 22만개를 얼마나 빠르게 소인수분해 하냐가 관건일 것 같다.

 

구현

1. 100만까지의 소수를 구하며 각 수의 소인수를 저장한다.
   factors 리스트에서 인덱스와 그 인덱스의 소인수의 값이 같다면 그 인덱스는 소수이다.
   완전히 소인수분해 하는 것이 아닌 약수 중 소수인 것을 찾는 과정이다.
2. 딕셔너리 변수 power를 선언한다. power는 A와 B의 소인수를 key로 하여 그 거듭제곱 값을 카운트 한다.
3. A와 B의 인수들에 대해 1에서 구한 소인수를 이용해 빠르게 소인수분해 하며 power에 저장한다.
   A에서는 거듭제곱의 카운트를 증가시키고 B에서는 감소시킨다.
4. power에 저장된 소인수와 그 거듭제곱 값을 이용해 분자와 분모를 분리하여 계산한다.

코드

factors = [[] for _ in range(1000001)]

def init_factors():
    for i in range(2,1000001):
        if factors[i]: continue # not prime

        factors[i].append(i)
        multi = i*2
        while multi <= 1000000:
            factors[multi].append(i)
            multi += i


def solve(a,b):
    power = dict()

    for factor in a:
        for prime in factors[factor]:
            if not prime in power: power[prime] = 0

            while factor % prime == 0:
                power[prime] += 1
                factor //= prime

    for factor in b:
        for prime in factors[factor]:
            if not prime in power: power[prime] = 0

            while factor % prime == 0:
                power[prime] -= 1
                factor //= prime
    

    numerator = 1
    denominator = 1

    for prime in power:
        if power[prime] > 0:
            numerator *= prime ** power[prime]
        else:
            denominator *= prime ** -power[prime]
    
    return numerator, denominator



init_factors()

for t in range(int(input())):
    input() # n,m is useless
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    numerator, denominator = solve(a,b)

    print("Case #%d:" %(t+1), numerator, "/", denominator)

후기

효율적인 코드를 찾는다고 머리 좀 썼다. 12초의 쓰레기 풀이는 덤.