Нужно решить задачу "Разбиение на квадраты"

Требуется представить заданное натуральное число N в виде суммы равных квадратов некоторого максимально возможного натурального числа M.
Входные данные
Входной файл INPUT.TXT содержит целое число N (1 ≤ N ≤ 2×109).
Выходные данные
В выходной файл OUTPUT.TXT выведите число – максимально возможный квадрат некоторого числа M. Если найти такое число невозможно, то выведите слово «impossible» (без кавычек).
Пример
№ Входные данные Выходные данные
1 180 36
Заранее огромное спасибо

Нужно провести факторизацию числа N. Если найдутся простые множители с кратностями более одного, то из них можно составить число M (или сразу квадрат числа M), а если все степени множителей равны единице, то ответ impossible.

Можете программу полностью скинуть?Пожалуйста.Просто факторизацию я ещё не изучал

factors.append(n)

Вот так?

а если такой код попробовать:

n = int(input())

max_square = 1

for i in range (2, n // 2):

  d_stepen = 0

  while(n % i == 0):
    d_stepen += 1
    n = n // i

  if d_stepen>1:
    max_square *=i**(d_stepen - (d_stepen%2))

if max_square==1:
    print('imposible')
else:
    print(max_square)
1 лайк

К сожалению неправильно

Ещё условия задачи таковы:
Время 1 сек
Память 16 МБ

А может быть надо прописать открытие файла INPUT.TXT и вывод в файл OUTPUT.TXT ?

ну и ошибку в слове надо исправить:

print('impossible')

@Sergebl, вместо range можно сделать:

i = 2
while i <= n:
    ...
    i += 1

Тогда будет меньше итераций.

Я новичок и не знаю будет ли в этом какой-нибудь смысл или нет

А для чего точки?

n = int(input())

max_square = 1

i = 2
while i <= n:
    i += 1

  while(n % i == 0):
    d_stepen += 1
    n = n // i

  if d_stepen>1:
    max_square *=i**(d_stepen - (d_stepen%2))

if max_square==1:
    print('impossible')
else:
    print(max_square)

Вот так?

какой-то контрольный пример код отрабатывает неверно.
такая задача есть на acmp номер 1788
при отправке этого кода выдаётся ошибка “Wrong answer” на тесте 4

Точки обозначают пропущенный код. Если вы делаете i += 1 в самом начале цикла, тогда нужно исправить i = 2 на i = 1. И данное исправление цикла не влияет на принятие этого решения автоматической системой проверки, если требуется работа с файлами вместо стандартных потоков ввода и вывода.

на acmp.ru открытие файлов в программе на python не требуется, я проверил сейчас. На других системах - не факт, нужно читать доки/смотреть примеры.
Но и если бы проблема была в файлах, то ошибка была бы сразу на первом же тесте

есть скользкий момент, когда число само является квадратом. например, для числа 64 или числа 400 какой должен быть ответ?

такой код acmp принял:

n = int(input())

max_square=0

i=1
while i<=int(n**0.5):

  if n % (i*i) == 0:
    max_square =i*i

  i += 1

if max_square==0:
    print('impossible')
else:
    print(max_square)

но в чём проблема в исходном примере - я так и не понял :cry:

Предположу в том, что impossible вариант недостижим. Всегда можно напечатать 1 как ответ, если ничего получше нет. А еще два вложенных цикла не проходят по времени. Короче говоря, не зря задачка в разделе для 7-8 класса :grinning_face_with_smiling_eyes:

1 лайк

Ошибка компиляции