题目描述
Mirko刚学会了如何求两个整数A和B的最大公约数。
由于A和B都非常大，所以我们不能直接给出，我们知道A是由N个正整数相乘得到的，我们也知道B是由M个正整数相乘得到的。
你的任务就是求A和B的最大公约数。
如果最大公约数超过9位，那么你只需要结果的后9位即可（如果后9位有前导0，则不需要输出前导0）。
输入输出格式
输入格式
第一行，一个整数N。(1 ≤ N ≤ 1000)。
第二行，N个正整数，这N个整数的乘积就等于A。每个正整数的范围：【1，1000000000】.
第三行，一个整数M。(1 ≤ M ≤ 1000)。
第四行，M个正整数，这M个整数的乘积就等于B。每个正整数的范围：【1，1000000000】.
输出格式
A和B的最大公约数。如果超过9位，输出后9位数字，如果后9位有前导0，则不需要输出前导0。
输入输出样例
输入样例
3
358572 83391967 82
3
50229961 1091444 8863
输出样例
12028
题解
这题a和b很大，所以不能直接用。
我们知道，给定一个大于1的正整数$a$，满足$a=\prod_{i=1}^{k}b_{i}^{p^{i}}$，那么我们可以分解题目中的a和b的质因数来求。