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

Python
#1

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

#2

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

#3

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

#4 
factors.append(n)

Вот так?

#5

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

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 лайк
#6

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

#7

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

#8

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

#9

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

print('impossible')
#10

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

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

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

#11

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

#12

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

#13 
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)

Вот так?

#14

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

#15

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

#16

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

#17

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

#18

такой код 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:

#19

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

1 лайк
#20

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