Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » ГП Ураины задача G
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Задача:
На доске записано N различных целых чисел, и каждый раз ребята выбирают некоторое подмножество и считают произведение всех чисел этого подмножества.
При выборе некоторых подмножеств в результате умножения получается полный квадрат. Ваша задача - определить количество непустых подмножеств, обладающих подобным свойством.
1 <= N <= 1000
1 <= Ai <= 1000
Видимо задача не сложная:) Решили ее многие. Но у меня что то по ней ничего не придумалось. Как решать?
Число является полным квадратом, если каждый простой делитель его входит в него с четной степенью.
Разложим все числа Ai на простые делители, тогда нас будут удовлетворять те подмножества чисел, у которых по каждому из простых делителей суммарная степень - четная.
Тогда получаем систему уравнений по модулю 2:
Переменные это x1, .., xn -- используем число или нет, а уравнение это для каждого простого числа p_i сумма по j = 1 .. n: степень p_i в числе a_j * x_j = 0.
Количество решений этой системы минус 1 (это то что непустых множеств) будет ответом задачи.
Количество решений это 2^(n - rankA), где rankA - это ранг матрицы соответствующей системе.
Спасибо. Думал капать нужно в другую сторону.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » ГП Ураины задача G