2015
04-16

# Big Division

A theoretical physicist friend is doing research about the "Answer to the Ultimate Question of Life, the Universe, and Everything", he thinks that it is not 42 as suggested by “The Hitchhiker’s Guide to the Galaxy” science fiction comedy series; instead he thinks it is the result of dividing the products of two sequences of positive integers A and B!
The task of calculating the product of A and B followed by division turned out to be not as easy as it looks, specially with the sequences being long and the products getting too large very quickly! Even using a modern computer, a straight forward implementation for the calculations may take very long time to complete! And this is where we seek your help as a brilliant computer scientist!

The first line of input contains an integer (1 <= T <= 200), the number of test cases.
T test cases follow, the first line of each test case contains two integers (1 <= N, M<= 110,000), the lengths of sequences A and B respectively. Two lines follow, the first line contains N space separated integers (0 < A0, A1 … An <= 1,000,000), and the second line contains M space separated integers (0 < B0, B1 … Bm <= 1,000,000).

The first line of input contains an integer (1 <= T <= 200), the number of test cases.
T test cases follow, the first line of each test case contains two integers (1 <= N, M<= 110,000), the lengths of sequences A and B respectively. Two lines follow, the first line contains N space separated integers (0 < A0, A1 … An <= 1,000,000), and the second line contains M space separated integers (0 < B0, B1 … Bm <= 1,000,000).

2
3 1
2 4 5
12
2 4
1 15
5 1 7 2

Case #1: 10 / 3
Case #2: 3 / 14

#define N 1000005
int max(int a,int b){return a>b?a:b;}
LL cnt[N];
void gao(int n,int p){
int i;
int a=1;
for(i=2;i*i<=n;i+=a,a=2){//加一个小优化，可以省下300ms，因为素因子中除了2,3相差1之外其它都至少相差2
if(n%i==0){
while(n%i==0){
cnt[i] += p;
n/=i;
}
}
}
if(n>1)cnt[n] += p;
}
int main(){
int t;
scanf("%d",&t);
int ca=1;
while(t--){
int n,m;
scanf("%d%d",&n,&m);
int i,j;
int a,b;
memset(cnt,0,sizeof(cnt));
int maxm = 0;
for(i=0;i<n;i++){
scanf("%d",&a);
maxm = max(a,maxm);
gao(a,1);
}
for(j=0;j<m;j++){
scanf("%d",&b);
maxm = max(b,maxm);
gao(b,-1);
}
int x = 1,y = 1;
for(i=2;i<=maxm;i++){
if(cnt[i] > 0){
while(cnt[i]--){
x *= i;
}
} else if(cnt[i]<0){
while(cnt[i]++){
y *= i;
}
}
}
printf("Case #%d: %d / %d\n",ca++,x,y);
}
return 0;
}