Ước chung lớn nhất

Xem PDF

Nộp bài


Điểm: 10 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 256M

Tác giả:
Dạng bài

Ước chung lớn nhất (Greatest Common Divisor - GCD) của hai hay nhiều số nguyên là số nguyên dương lớn nhất là ước chung của các số đó. Ví dụ: \(GCD(12, 20, 28) = 4\).

Hôm nay trong tiết Toán, thầy giáo yêu cầu tính GCD của hai số nguyên dương \(X\) và \(Y\), nhưng vì hai số này rất lớn nên thầy đã tách chúng thành tích của các số nguyên dương nhỏ hơn để dễ tính toán. \(X\) được tách thành tích của \(N\) số nguyên dương, và \(Y\) được tách thành tích của \(M\) số nguyên dương.

Mặc dù là thành viên đội tuyển quốc gia, nhưng vì đang tương tư CD, hyxinchou không còn tâm trí để giải bài tập này, đành phải nhờ đến các bạn học viên của TKPC. Hãy giúp anh ấy nhé!

Input

  • Dòng đầu chứa số nguyên dương \(N\);
  • Dòng thứ hai chứa \(N\) số nguyên dương \(x_1,\ x_2,\ldots,\ x_N\) mà có tích bằng \(X\);
  • Dòng đầu chứa số nguyên dương \(M\);
  • Dòng thứ hai chứa \(M\) số nguyên dương \(y_1,\ y_2,\ldots,\ y_N\) mà có tích bằng \(Y\).

Output

  • In ra một số là \(GCD(X,Y)\). Nếu kết quả có nhiều hơn \(9\) chữ số, chỉ in ra \(9\) chữ số cuối.

Ví dụ

Sample input 1
5   
6 7 5 3 2
4
8 4 6 10
Sample output 1
60

Sample input 2
2
10 21
1
15
Sample output 2
15

Sample input 3
3
2328655 9680 1037
4
465731 11664 1815848 2530
Sample output 3
000440080

Ràng buộc

  • \(1\leq N,\ M\leq10^3\);
  • \(1\leq x_i,\ y_i\leq10^9\).