Плитки Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт В магазине продаются плитки размером 1×1 упаковками по X штук. Какое минимальное количество упаковок надо купить, чтобы замостить плитками некоторый квадрат с целочисленными сторонами? Все плитки из купленных упаковок должны быть использованы.

Для того чтобы замостить квадрат, нам нужно найти наименьшее общее кратное чисел X и Y (сторона квадрата), так чтобы получившееся число было квадратом целого числа.

То есть, нам нужно найти наименьшее общее кратное чисел X и Y, которое является квадратом целого числа.

Например, если X = 3, то наименьшее общее кратное для X и Y будет 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, ... и так далее. Если мы возьмем Y = 6, то наименьшее общее кратное для X и Y будет 6, 12, 18, 24, 30, ... и так далее. Таким образом, наименьшее общее кратное для X = 3 и Y = 6 будет 6.

Итак, чтобы решить эту задачу, мы можем использовать следующий алгоритм:

1. Найти наименьшее общее кратное для X и Y.
2. Проверить, является ли полученное число квадратом целого числа.
3. Если да, то это и будет минимальное количество упаковок, которые нам нужно купить. Если нет, то увеличить Y на 1 и повторить шаги 1-2.

Пример кода на Python:

import math

def lcm(x, y):
    return x * y // math.gcd(x, y)

def min_packages(x):
    y = 1
    while True:
        lcm_xy = lcm(x, y)
        sqrt_lcm_xy = int(math.sqrt(lcm_xy))
        if sqrt_lcm_xy * sqrt_lcm_xy == lcm_xy:
            return lcm_xy // x
        y += 1

X = int(input())
print(min_packages(X))

Этот код найдет минимальное количество упаковок, которые нужно купить, чтобы замостить квадрат плитками размером 1x1.