9765(여섯 방정식) - 시간 초과 - 참고 - 해결

여섯 방정식

 

문제

여섯 개의 간단한 방정식이 주어진다. 이때, x1, x2, x3, x5, x6, x7를 찾는 프로그램을 작성하시오. x1, x2, x3, x5, x6, x7은 2보다 크거나 같고, 20,000,000보다 작거나 같은 소수이다. 여섯 방정식은 아래와 같다.

• c1 = x1x2
• x4 = c4x1
• c3 = x6x7
• x8 = x7c2
• c5 = x2x3
• c6 = x6x5

c1, c2, c3, c4, c5, c6은 양의 정수로 (20,000,000)2을 넘지 않는다. c1, c2, c3, c4, c5, c6이 주어졌을 때, x1, x2, x3, x5, x6, x7을 푸는 프로그램을 작성하시오. 항상 풀 수 있는 방정식만 입력으로 주어진다.

 

입력

첫째 줄에 c1, c2, c3, c4, c5, c6이 주어진다. (c1 ≠ c5, c3 ≠ c6)

 

출력

x1, x2, x3, x5, x6, x7 를 공백으로 구분해 출력한다. 가능한 답이 여러 가지인 경우, 아무거나 출력한다.

---

원래는 약수 찾는 방식으로 하였지만 그렇게 하니 50%에서 시간 초과가 났다.

import sys

C = [0] + list(map(int,sys.stdin.readline().split()))

X123 = []
C1C5 = C[1] * C[5]
X567 = []
C3C6 = C[3] * C[6]
i = 2
while i < max(int((C[3] * C[6])**(1/2)),int((C[1] * C[5])**(1/2)))+1:
    if C1C5 % i == 0:
        X123.append(i)
        C1C5 //= i
    if C3C6 % i == 0:
        X567.append(i)
        C3C6 //= i

    if C1C5 == 1 and C3C6 == 1:
        break
    i += 1


for i in range(4):
    if X123.count(X123[i]) == 2:
        X2 = X123[i]
        X123.remove(X2)
        X123.remove(X2)

    if X567.count(X567[i]) == 2:
        X6 = X567[i]
        X567.remove(X6)
        X567.remove(X6)
        
X1 = X123[0]
X3 = X123[1]
X5 = X567[0]
X7 = X567[1]
print(X1,X2,X3,X5,X6,X7)

그래서 알고리즘을 확인해보니 유클리드 호제법이 있길래 해당 기법은 배웠던 개념이라 간단히 다시보고 해보니 바로 통과 하였다.

import sys

# C 저장
C = [0] + list(map(int,sys.stdin.readline().split()))

# 유클리드 호제법
def gcd(a,b):
    while b:
        a, b = b, a % b
    return a

# 크기 비교 후 gcd 구하기 
if C[1] > C[5]:
    X2 = gcd(C[1],C[5])
else:
    X2 = gcd(C[5],C[1])
X1 = C[1]//X2
X3 = C[5]//X2
# 크기 비교 후 gcd 구하기 
if C[3] > C[6]:
    X6 = gcd(C[3],C[6])
else:
    X6 = gcd(C[6],C[3])
X5 = C[6]//X6
X7 = C[3]//X6     

print(X1,X2,X3,X5,X6,X7)