Sherlock And Large Numbers - I

0

0 votes
Prime Factorization, Medium
Problem

Moriarty has challenged Sherlock with a complicated maths problem. Moriarty will provide Sherlock two arrays a and b. Sherlock should multiply all the numbers in a, which will form a large number A. Then Sherlock should multiply all the numbers in b, which will form a large number B. Sherlock needs to find two positive integers p and q, such that q*A=p*B and gcd(p, q) = 1. Since, p and q will also be large numbers, Moriarty wants the value of p modulo 1000000007(1e9 + 7) and q modulo 1000000007(1e9 + 7).

Note:- Here, gcd(a , b) indicates greatest common divisor of a and b. Learn about gcd here.

Learn how to answer modulo 1000000007 here.

Note:- Python has not been allowed for this problem as python provides some features that hides the main motive for this problem. Sorry for the inconvenience.

Note:- Use of fast I/O is recommended.

See the sample case for better understanding.


Input format:

First line contains an integer T, denoting the number of test-cases.

Next 3T lines contain the test-cases as shown below:-

First line contains two integers n and m, representing the sizes of arrays a and b respectively.

Second line contains n space separated integers(a1, a2, ... an). Here, ai indicates ith element of array a.

Third line contains m space separated integers(b1, b2, ... bm). Here, bi indicates ith element of array b.


Output format:

For each testcase, print values of p modulo 1000000007(1e9 + 7) and q modulo 1000000007(1e9 + 7) in a new line.


Constraints:

1 <= T <= 10

1 <= n, m <= 100000

1 <= ai, bi <= 1000000(1e6)


Subtasks:

Subtask #1 (10 points) : n = m = 1

Subtask #2 (10 points) : A, B <= 1e18

Subtask #3 (10 points) : 1 <= n, m <= 100

Subtask #4 (10 points) : 1 <= n, m <= 1000

Subtask #5 (60 points) : Original Constraints

Time Limit: 1.5
Memory Limit: 256
Source Limit:
Explanation

In first testcase, A = 4 and B = 6. Now, let p=2 and q=3. Here, gcd(2, 3) = 1 and q*A = 3*4 = p*B = 2*6 = 12. So, answer is p = 2 and q = 3.

In second testcase, A = 2 * 6 = 12 and B = 13. Now, gcd(A, B) = 1 and A*B = B*A. Hence, answer is p=A=12 and q=B=13.

Editor Image

?