Algorithm PS/Algospot
[Algospot] 정수론 / POTION / Python 파이썬
migrationArc
2021. 10. 4. 09:30
https://www.algospot.com/judge/problem/read/POTION#
풀이
주어진 정수 배열의 최대공약수를 구하여 해결하는 문제이다.
최대공약수를 구하기위해 유클리드 알고리즘 을 활용하였다.
c = int(input())
def get_gcd(p, q):
if q == 0:
return p
return get_gcd(q, p % q)
def get_r_gcd(r_list):
for i in range(1000, 0, -1):
flag = 1
for r in r_list:
if get_gcd(i, r) != i:
flag = 0
break
if flag:
return i
def get_answer(r_list, p_list, n):
cnt = 1
while True:
flag = 1
for i in range(n):
if r_list[i] * cnt < p_list[i]:
flag = 0
break
if flag:
break
cnt += 1
temp = [0] * n
for i in range(n):
temp[i] = r_list[i] * cnt - p_list[i]
return temp
return cnt
for _ in range(c):
n = int(input())
# 필요한 재료 량
r_list = list(map(int, input().split()))
r_gcd = get_r_gcd(r_list)
gcd_r_list = [r // r_gcd for r in r_list]
p_list = list(map(int, input().split()))
answer = get_answer(gcd_r_list, p_list, n)
print(" ".join(map(str, answer)))