파이썬 2824 백준

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

2824번: 최대공약수

 

 

최대공약수 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

192 MB

7918

1571

1211

27.037%

문제

상근이는 학생들에게 두 양의 정수 A와 B의 최대공약수를 계산하는 문제를 내주었다. 그런데, 상근이는 학생들을 골탕먹이기 위해 매우 큰 A와 B를 주었다.

상근이는 N개의 수와 M개의 수를 주었고, N개의 수를 모두 곱하면 A, M개의 수를 모두 곱하면 B가 된다.

이 수가 주어졌을 때, 최대공약수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다.

셋째 줄에 M(1 ≤ M ≤ 1000)이 주어진다. 넷째 줄에는 M개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, M개의 수를 곱하면 B가 된다.

출력

두 수의 최대공약수를 출력한다. 만약, 9자리보다 길다면, 마지막 9자리만 출력한다. (최대 공약수가 1000012028인 경우에는 000012028을 출력해야 한다)

예제 입력 1 복사

3
2 3 5
2
4 5

예제 출력 1 복사

10

예제 입력 2 복사

4
6 2 3 4
1
1

예제 출력 2 복사

1

예제 입력 3 복사

3
358572 83391967 82
3
50229961 1091444 8863

예제 출력 3 복사

000012028

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #2 3번

• 문제를 번역한 사람: baekjoon
• 어색한 표현을 찾은 사람: doju
• 데이터를 추가한 사람: yuja

알고리즘 분류

• 수학
• 구현
• 정수론
• 소수 판정

 

 

아래는 내가 푼 방식.

유클리드호제법으로 최대공약수 구하면 간단히 풀림.

def gcd(x,y):
    while y>0:
        x, y = y, x%y
    return x


x = int(input())
x_arr = list(map(int,input().split()))

A=1

for i in x_arr:
    A= A * i

y = int(input())
y_arr = list(map(int,input().split()))

B=1

for i in y_arr:
    B= B * i


answer = str(gcd(A,B))
print(answer[-9:])