Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1873. Factorial Simplification
Специальные системы счисленияОлимпиадные задачи на английском языке
| 05/11/2012 | Тренировка (задачи NEERC 2010) (F) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Peter is working on a combinatorial problem. He has carried out quite lengthy derivations
and got a resulting formula that is a ratio of two products of factorials like this:
`{p_1!\ p_2!\ …\ p_n!}/{q_1!\ q_2!\ …\ q_m!}`
This does not surprise Peter, since factorials appear quite often in various combinatorial formulae,
because `n!` represents the number of transpositions of `n` elements — one of the basic
combinatorial objects.
However, Peter might have made a mistake in his derivations. He knows that the result should
be an integer number and he needs to check this first. For an integer result Peter wants
to simplify this formula to get a better feeling of its actual combinatorial significance. He
wants to represent the same number as a product of factorials like this.
`r_1!^{s_1}\ r_2!^{s_2}\ …\ r_k!^{s_k}\ t`
where all `r_i` are distinct integer numbers greater than one in the descending order
(`r_i\ >\ r_{i+1}\ >\ 1`), `s_i` and `t` are positive integers.
Among all the possible representations
in this form, Peter is interested in one where `r_1` is the largest possible number, among
those in the one where `s_1` is the largest possible number; among those in the one
where `r_2` is the largest possible number; among those in the one where `s_2` is the
largest possible number; etc, until the remaining `t` cannot be further represented in this form.
Peter does not care about the actual value of `t`. He wants to know what is the factorial-product part
of his result.
The first line of the input file contains two integer numbers `n` and `m` (`1\ ≤\ n,\ m\ ≤\ 1000`).
The second line of the input file contains `n` integer numbers `p_i` (`1\ ≤\ p_i\ ≤\ 10\ 000`) separated by spaces.
The third line of the input file contains `m` integer numbers `q_i` (`1\ ≤\ q_i\ ≤\ 10\ 000`) separated by spaces.
On the first line of the output write a single integer number `k`. Write `k\ =\ -1` if the ratio of the
given factorial products is not an integer. Write `k\ =\ 0` if the ratio is an integer but it cannot be represented
in the desired form. Write `k\ >\ 0` followed by `k` lines if the ratio can be represented by a factorial
product as described in the problem statement. On each of the following `k` lines write two integers
`r_i` and `s_i` (for `i\ =\ 1,…,k`) separated by a space.
Sample Input #1
1 2 6 4 4
Sample Output #1
-1
Sample Input #2
1 2 6 3 4
Sample Output #2
0
Sample Input #3
4 2 9 2 2 2 3 4
Sample Output #3
2 7 1 2 2
