Квадратные наборы в числах от 1 до 20

Question

Даны натуральные числа от 1 до 20. Среди них можно выбрать те числа, произведение которых будет полным квадратом (квадратный набор) . Необходимо найти обще число таких вариантов.
Например: 16*1*2*8 - полный квадрат, 7*14*18*10*5*2 - полный квадрат (числа в таких наборах различны) . И нужно найти обще количество таких вариантов. Ясно, что простые числа 11, 13, 17, 19 можно тут не рассматривать и сразу исключить их. Но вот с простыми множителями 2, 3, 5, 7 не все так просто, ибо вариантов там достаточно много и никакой симметрии не наблюдается. Есть ли какой-то красивый и неочевидный способ как посчитать количество таких комбинаций? Я пытался прибегать к теории вероятности, чтобы, найдя вероятность двумя способами, определить количество таких чисел. Но ничего не вышло. Осложняет задачу тот факт, что некоторые полные квадраты могут быть получены различными комбинациями карточек, но не все. Задачу нужно решить математически не используя программирование. Запрограммировать тут я и сам смог бы.

Answer 1

Там как. если произведение двух чисел, разных и отличных от 1, будет квадратом, значит этот квадрат можно разложить на 2 квадрата. То есть если мы на что-то умножаем 3, чтобы получить квадрат, это второе число должно делиться на 3, а частное будет квадратом, 3 умножить. на что? На 2*2, будет 12, а следующий множитель, 3*3*3, будет уже больше 20

Answer 2

Вам надо рассматривать простые числа (2, 3, 5, 7, 11, 13, 17, 19) . Понять и использовать "осн теорему т. ч. " - любое число представимо в виде произведения простых в степени (нач с 0) . Что бы был квадрат - все степени чётные, ну и ограничиться вариантами, когда можно сгруппировать сомножители как числа не боле 20.
Комбинаторная, не очень простая, задача.