Least Multiple

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Given a positive integer M, Bob needs to find the minimum positive integer N so that N! \equiv 0 \pmod{M}.

Since M is huge, Bob will give you K integers, denoted as e_1, e_2, \ldots, e_K, such that M = \prod_{i=1}^{K} p_i^{e_i}, where p_i is the i-th smallest prime number. It is guaranteed that p_i \cdot e_i \le 10^{18}

Input Specification

The first line of input contains an integer T (1 \le T \le 10^4), the number of test cases.

Each of the following T blocks contains two lines of input. The first line contains an integer K (1 \le K \le 100), the number of prime factors. The second line contains K integers e_i (0 \le p_i \cdot e_i \le 10^{18}), indicating the i-th prime's exponent.

Output Specification

Output one integer for each test case, the smallest positive integer N so that N! \equiv 0 \pmod{M}.


Subtask Points Additional constraints
1 10 T = 1, p_i \cdot e_i \le 10^5.
2 25 T \le 1000, p_i \cdot e_i \le 1000.
3 30 T \le 10^3, p_i \cdot e_i \le 10^{18}.
4 35 No additional constraints.

Sample Input

1 1 1 1 1

Sample Output



M = 2^1 \times 3^1 \times 5^1 \times 7^1 \times 11^1 = 2310, and the minimum N is 11.


There are no comments at the moment.