[BOJ] 9359 서로소 python

 

이 문제를 풀면서 가장 어려운 점 중 하나는, 메모리 관리인 것 같다.

 

메모리 관리와 시간을 얼마나 잘 활용하느냐에 따라서 이 문제를 풀 수 있는지가 나뉘겠다.

 

 

처음 풀었던게 25일전이었다 ... 복기에 꽤 시간이 많이 걸렸던 것 같다.

 

하여튼, 잘 문제를 풀어서 기분은 꽤 좋은 편이다.

 

이 문제를 푸는 과정에 있어서 주의해야할 과정이 있다 (메모리와 시간 관리에 있어서)

 

첫번째로,

 

 

def prime_set(n):
    if n == 2:
        return [2]
    if n == 3:
        return [3]
    prime = []
    t = int(math.sqrt(n)) + 1
    num = [False for i in range (0,t+1)]
    for i in range (2,t+1):
        if num[i] == False:
            prime.append(i)
            for j in range (i, t+1, i):
                num[j] = True
    return prime
#prime은 소수를 저장하고 있는 집합

 

위 과정에서는 주어진 n까지의 소수를 취하고 싶은 상황인데, n까지의 집합을 취하게 되면 꼭 도중에 메모리가 터지게 되는 것 같았다.

그래서, 메모리 관리를 해주는 법으로,  t를 저렇게 정리해둔 다음에, t까지의 소수들을 전부 취해준다.

나머지 것들은 이후에 핸들링 해주는 것으로 저렇게 얻어낸다.

def ofprime(n):
    prime = []
    t =  prime_set(n)
    for i in range (0,len(t)):
        if n % t[i] == 0:
            prime.append(t[i])
            while n % t[i] == 0:
                n //= t[i]
    if n != 1:
        prime.append(n)
    return prime

 

ofPrime이라는 함수를 통해서, n의 소인수들을 얻어줄 것이다. 이 과정에서 위에서 구한 prime_set을 활용하겠다.

 

여기서 중요한 점으로서, 마지막 조건문인 n!= 1이라면 n을 추가해주는 것. 이게 핵심인 부분이다.

 

예를 들어 주어진 수 n이 합성수라면, n =   a x b라는 형식으로 얻어질텐데, 일반성을 잃지 않고 a <= b라고 둘 수 있겠다.

저말이 무슨 뜻이냐면, 만약 n의 제곱근정도까지의 소수로 안 나눠떨어졌다 ! 그러면 n은 반드시 소수여야만 한다는 것

 

이후의 과정은 포함배제의 원리를 사용하면 되겠다.

이거는 아래에 추가로 기재해두겠다.

 

import sys
from itertools import combinations
import math
input = sys.stdin.readline

def prime_set(n):
    if n == 2:
        return [2]
    if n == 3:
        return [3]
    prime = []
    t = int(math.sqrt(n)) + 1
    num = [False for i in range (0,t+1)]
    for i in range (2,t+1):
        if num[i] == False:
            prime.append(i)
            for j in range (i, t+1, i):
                num[j] = True
    return prime
#prime은 소수를 저장하고 있는 집합

def ofprime(n):
    prime = []
    t =  prime_set(n)
    for i in range (0,len(t)):
        if n % t[i] == 0:
            prime.append(t[i])
            while n % t[i] == 0:
                n //= t[i]
    if n != 1:
        prime.append(n)
    return prime

T = int(input())
for case in range (0,T):
    a,b,N = map(int,input().split())
    cnt1,cnt2 = a-1,b
    prime = ofprime(N)
    for i in range (1,len(prime)+1):
        k = list(combinations(prime,i))
        k = list(set(k))
        for comb in k:
            t = 1
            for j in range (0,len(comb)):
                t *= comb[j]

            #t로 나누겠다는 뜻
            if i % 2 != 0:
                cnt1 -= (a-1) // t
                cnt2 -= b // t
            else:
                cnt1 += (a-1) // t
                cnt2 += b // t
    print(f'Case #{case + 1}: {(cnt2 - cnt1)}')

 

 

간만에 기분 좋게 풀었던 문제가 되겠다. 꽤 오래된 체증이 내려가는 느낌....

 

내일부터는 계약직으로 일을 시작하게 되는데, 코딩 역량도 키우면서 운동도 해보고, 바쁜 삶을 한동안 살아봐야겠다. 

 

화이팅 !