Đế chế phản công

Điểm: 8,00 (OI)

Giới hạn thời gian: 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho $k$ số nguyên dương $a_{1}, a_{2}, \dots, a_{k}$ . Hãy tìm số nguyên dương $n$ nhỏ nhất sao cho biểu thức

$\frac{n!}{a_{1}! \cdot a_{2}! \dots a_{k}!}$

là một số nguyên dương.

Dòng đầu chứa số nguyên $k$ ( $1 \leq k \leq 10^{6}$ ).
Dòng thứ hai chứa $k$ số nguyên $a_{1}, a_{2}, \dots, a_{k}$ ( $1 \leq a_{i} \leq 10^{7}$ ).

In ra một số nguyên duy nhất là giá trị nhỏ nhất của $n$ thỏa mãn.

Input	Output	Giải thích
2 1000 1000	2000	Với $n = 2000$ , $\frac{2000!}{1000! \cdot 1000!} = (\binom{2000}{1000})$ là số nguyên dương. Với mọi $n < 2000$ , biểu thức không nguyên (chẳng hạn không đủ thừa số nguyên tố $5$ trong $n!$ ).
1 2	2	Với $n = 2$ : $\frac{2!}{2!} = 1$ .
2 65537 65537	131074	Cần $n$ chia hết đủ thừa số nguyên tố lớn nhất là $65537$ , nên $n \geq 2 \cdot 65537 = 131074$ .

Bình luận

Không có bình luận tại thời điểm này.