Проверка состояния

Автор задачи: Антон Вдовин, разработчик: Даниил Голов

В первой подгруппе все числа в массиве не превосходят $$$10$$$, $$$10! = 3 628 800$$$, а значит, подойдёт решение просто посчитать факториал каждого $$$a_i$$$, взять их наибольший общий делитель и проверить на равенство с факториалом $$$gcd(a)$$$, который, очевидно, тоже не будет превышать $$$10!$$$.

Во второй подгруппе имелось всего два числа, называем их $$$a$$$ и $$$b$$$. Заметим, что $$$gcd(a!, b!) = min(a, b)!$$$. Также заметим, что $$$min(a, b)$$$ совпадает с $$$gcd(a, b)$$$ когда $$$a | b$$$ или $$$b | a$$$. Таким образом, достаточно было проверить, что $$$a$$$ делится нацело на $$$b$$$ или $$$b$$$ делится нацело на $$$a$$$.

В третьей подгруппе имелось три числа $$$a$$$, $$$b$$$, $$$c$$$. Чтобы получить решение, переберём все возможные пары из трёх чисел и применим логику из подгруппы $$$2$$$.

Для полного решения необходимо было лишь заметить тот факт, что $$$gcd(a_1!, a_2!, \dots a_n!) = min(a_1, a_2, \dots a_n)!$$$ для любого $$$n$$$. Действительно, возьмем факториал минимального числа из $$$a$$$. Очевидно, он будет меньше любого другого факториала числа из $$$a$$$, а также будет делить любой факториал из $$$a$$$, так как любой факториал из $$$a$$$ — это минимальный факториал, умноженный ещё на несколько последовательных натуральных чисел. Получаем, что $$$min(a)! = gcd(a)!$$$. Сократим на факториал, получим $$$min(a) = gcd(a)$$$. Проверка этого условия тривиальна и её возможно сделать не используя ни вычисления наибольшего общего делителя, ни факториала.