题目链接：http://www.spoj.com/problems/HG/
题目大意：分别给N个和M个小于等于1e9的数，前N个数相乘为A，后M个数相乘为B，问你GCD(A, B) 1<= N<= 1000，1 <=M <= 1000
解题思路：枚举a[i] 和b[i]，计算两者GCD，然后结果乘以GCD，两者都除以GCD。最后判断一下如何输出即可。
代码：
1 const int maxn = 1e4 + 5; 2 int n, m; 3 ll a[maxn], b[maxn]; 4 5 int gcd(int x, int y){ 6 return y == 0? x: gcd(y, x % y); 7 } 8 void solve(){ 9 ll ans = 1; 10 bool flag = false; 11 for(int i = 0; i < n; i++){ 12 for(int j = 0; j < m; j++){ 13 int tmp = gcd(a[i], b[j]); 14 a[i] /= tmp; b[j] /= tmp; 15 ans *= tmp; 16 if(ans >= mod){ 17 flag = true; 18 ans %= mod; 19 } 20 } 21 } 22 if(flag) printf("%09lld ", ans % mod); 23 else printf("%lld ", ans); 24 } 25 26 int main(){ 27 scanf("%d", &n); 28 for(int i = 0; i < n; i++) scanf("%lld", &a[i]); 29 scanf("%d", &m); 30 for(int i = 0; i < m; i++) scanf("%lld", &b[i]); 31 solve(); 32 }
题目：
HG - HUGE GCD
RK has received a homework assignment to compute the greatest common divisor of the two positive integers Aand B. Since the numbers are quite large, the professor provided him with N smaller integers whose product is A, and M integers with product B.
RK would like to verify his result, so he has asked you to write a program to solve his problem. If the result is more than 9 digits long, output only the last 9 digits.
INPUT
The first line of input contains the positive integer N (1<= N<= 1000).
The second line of input contains N space-separated positive integers less than 10^9, whose product is the number A.
The third line of input contains the positive integer M (1 <=M <= 1000).
The fourth line of input contains M space-separated positive integers less than 10^9, whose product is the number B.
OUTPUT
The first and only line of output must contain the greatest common divisor of numbers A and B. If the result is more than 9 digits long, output only the last (least significant) 9 digits.
SAMPLE
Input
3
2 3 5
2
4 5
Output
10
Input
3
358572 83391967 82
3
50229961 1091444 8863
Output
000012028
First sample description: The greatest common divisor of numbers A = 30 and B = 20 equals 10.