Плитки Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт В магазине продаются плитки размером 1×1 упаковками по X штук. Какое минимальное количество упаковок надо купить, чтобы замостить плитками некоторый квадрат с целочисленными сторонами? Все плитки из купленных упаковок должны быть использованы. Формат входных данных В единственной строке вводится целое число X (1≤X≤1012 ). Обратите внимание, что ответ может превышать возможное значение 32 ‑битной целочисленной переменной, поэтому необходимо использовать 64 ‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#). Формат выходных данных Выведите минимальное количество упаковок, которое надо купить. Можно доказать, что такое число всегда существует. Система оценки Решения, правильно работающие при X≤1000 , будут оцениваться в 40 баллов. Замечание В примере в каждой упаковке по 12 плиток. Если мы купим одну упаковку, то не сможем замостить квадрат. Если купим 2 упаковки, то получится 24 плитки, которыми тоже нельзя замостить ни один квадрат. Если же купить 3 упаковки, то получится 36 плиток, ими можно замостить квадрат размера 6×6 . Ввод Вывод 12 3

Чтобы решить эту задачу, давайте разберем её шаг за шагом.

Мы имеем плитки размером 1×1, упакованные по X штук. Задача заключается в том, чтобы определить минимальное количество упаковок, необходимых для того, чтобы замостить квадрат с целочисленными сторонами.

1. Квадрат и его площадь: Площадь квадрата со стороной N равна \(N^2\). Для того чтобы замостить его плитками, необходимо, чтобы общее количество плиток, которое мы покупаем, было равно \(k \times X\) (где k – количество упаковок), и это количество плиток должно быть равно \(N^2\).

2. Определение минимального k: Мы должны найти такое минимальное k, что \(k \times X\) является квадратом. То есть, \(k \times X = m^2\) для некоторого целого числа m.

3. Приведение к квадрату: Поскольку \(k \times X\) должно быть квадратом, мы можем выразить это следующим образом: необходимо найти минимальное целое число k, такое что \(k\) является целым квадратом, множителем \(X\).

4. Нахождение подходящего k:

   • Разложим \(X\) на простые множители.
   • Для каждого простого множителя, если его степень нечетная, нам нужно добавить 1 к этой степени (чтобы сделать её четной), и это приведет к увеличению соответствующего множителя на 1.
   • Затем мы перемножаем все эти множители, чтобы получить значение k.

Пример: Если \(X = 12\),

• Разложение на простые множители: \(12 = 2^2 \times 3^1\).
• У нас 2 в четной степени и 3 в нечетной степени. Следовательно, мы добавляем 1 к степени 3, получая \(3^2\).
• Мы берем наименьшее количество упаковок: \(k = 3\), так как \(12 \times 3 = 36\), что является квадратом \(6 \times 6\).

Общая формула: Найдите \(k\) из \(X\), используя его простое разложение. Затем перемножьте полученные множители.

Теперь напишем алгоритм на основе этих шагов:

def min_packages(X):
    import math

    k = 1
    # Проверяем делимость X на 2
    while X % 2 == 0:
        X //= 2
    # Проверяем, осталась ли нечетная степень
    if X % 2 != 0:
        k *= 2
        
    # Проверяем делимость на остальные простые числа
    for i in range(3, int(math.sqrt(X)) + 1, 2):
        count = 0
        while X % i == 0:
            X //= i
            count += 1
        if count % 2 != 0:
            k *= i

    if X > 1:
        k *= X

    return k

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

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