Разбиение на квадраты

@GHGEJGK · Регистрация: 17.01.2022

Студворк — интернет-сервис помощи студентам

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

@thyrex · 01.05.2022, 11:31

Если я все правильно понял, то вариант с impossible не сработает никогда, ибо любое натуральное число можно предствить в виде суммы n единиц

Python
1
2
3
4
5
n = int(input('n = '))
i = int(n**0.5)
while i>0 and n%(i**2):
    i -= 1
print(i**2)

@GHGEJGK · 01.05.2022, 11:41 **[ТС]**

Неправильный ответ пишут.Время: 1 сек, память 16 Мб

@thyrex · 01.05.2022, 11:48

И на каком тесте на acmp неверный ответ?

@GHGEJGK · 01.05.2022, 12:00 **[ТС]**

На 1

Добавлено через 1 минуту
Здесь N=180, а M=6. Действительно: 180 = 36+36+36+36+36 = 6^2+6^2+6^2+6^2+6^2, большего такого слагаемого как 36 не существует.

@thyrex · 01.05.2022, 12:00

Может все потому, что вы не организуете файловый ввод-вывод, как это требуется на acmp?

@GHGEJGK · 01.05.2022, 12:27 **[ТС]**

file = open('input.txt')
n = int(input('n = '))
i = int(n**0.5)
while i>0 and n%(i**2):
i -= 1
fout = open('output.txt')
Вот так?

@thyrex · 01.05.2022, 15:05

Нет. Примеры работы с файлами можно увидеть даже в недавних темах в этом разделе, всего-то нужно захотеть это сделать

@GHGEJGK · 02.05.2022, 09:06 **[ТС]**

n = int(input())
i = int(n)**1
while i>0 and n%(i**2):
i-=1
print(i**2)
Моя прога 13 тестов прошла,а потом по времени не успела

@eaa · 02.05.2022, 09:14

GHGEJGK, проверяй до корня

Добавлено через 3 минуты

Python
1
2
3
4
5
6
7
8
n = int(input())
i = 1
ans = 0
while i * i <= n:
    if n % i ** 2 == 0:
        ans = i * i
    i += 1
print(ans)

@GHGEJGK · 02.05.2022, 09:16 **[ТС]**

А что проверить?Вот время моей программы1,218

@eaa · 02.05.2022, 09:18

а у тебя счетчик вниз идет, тогда проверяй от корня из n

@thyrex · 02.05.2022, 09:23

eaa, в сообщении №2 автору и был дан вариант проверки вниз от корня из n

@Gdez · 02.05.2022, 09:37

Как вариант

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = 10001400049 #int(input())
d = 2
res = 1
while d < n:
    if not(n%d):
        c = 1
        n //= d
        while not(n%d):
            n //= d 
            c += 1
        c -= c%2
        res *= d**c
    d += 1
print(res)

@thyrex · 02.05.2022, 11:35

Python
1
2
3
4
5
6
7
8
9
10
11
fin = open('input.txt')
fout = open('output.txt', 'w')
 
n = int(fin.readline())
i = int(n**0.5)
while i>0 and n%(i**2):
    i -= 1
fout.write(str(i**2))
 
fin.close()
fout.close()

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод https:/ / **********/ gallery/ thinkpad-x220-tablet-porn-gzoEAjs . . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

@GHGEJGK 1 / 1 / 0 Регистрация: 17.01.2022 Сообщений: 41

	Разбиение на квадраты 01.05.2022, 10:37. Показов 2231. Ответов 14 Метки нет (Все метки) Требуется представить заданное натуральное число N в виде суммы равных квадратов некоторого максимально возможного натурального числа M. Входные данные Входной файл INPUT.TXT содержит целое число N (1 ≤ N ≤ 2×10⁹). Выходные данные В выходной файл OUTPUT.TXT выведите число – максимально возможный квадрат некоторого числа M. Если найти такое число невозможно, то выведите слово «impossible» (без кавычек). Пример № Входные данные Выходные данные 1 180 36 0

@GHGEJGK 1 / 1 / 0 Регистрация: 17.01.2022 Сообщений: 41
	01.05.2022, 11:41 [ТС]
	Неправильный ответ пишут.Время: 1 сек, память 16 Мб 0

@thyrex 14433 / 7475 / 1579 Регистрация: 06.09.2009 Сообщений: 27,112
	01.05.2022, 11:48
	И на каком тесте на acmp неверный ответ? 0

@GHGEJGK 1 / 1 / 0 Регистрация: 17.01.2022 Сообщений: 41
	01.05.2022, 12:00 [ТС]
	На 1 Добавлено через 1 минуту Здесь N=180, а M=6. Действительно: 180 = 36+36+36+36+36 = 6^2+6^2+6^2+6^2+6^2, большего такого слагаемого как 36 не существует. 0

@thyrex 14433 / 7475 / 1579 Регистрация: 06.09.2009 Сообщений: 27,112
	01.05.2022, 12:00
	Может все потому, что вы не организуете файловый ввод-вывод, как это требуется на acmp? 0

@GHGEJGK 1 / 1 / 0 Регистрация: 17.01.2022 Сообщений: 41
	01.05.2022, 12:27 [ТС]
	file = open('input.txt') n = int(input('n = ')) i = int(n0.5) while i>0 and n%(i2): i -= 1 fout = open('output.txt') Вот так? 0

@thyrex 14433 / 7475 / 1579 Регистрация: 06.09.2009 Сообщений: 27,112
	01.05.2022, 15:05
	Нет. Примеры работы с файлами можно увидеть даже в недавних темах в этом разделе, всего-то нужно захотеть это сделать 0

@GHGEJGK 1 / 1 / 0 Регистрация: 17.01.2022 Сообщений: 41
	02.05.2022, 09:06 [ТС]
	n = int(input()) i = int(n)1 while i>0 and n%(i2): i-=1 print(i**2) Моя прога 13 тестов прошла,а потом по времени не успела 0

@GHGEJGK 1 / 1 / 0 Регистрация: 17.01.2022 Сообщений: 41
	02.05.2022, 09:16 [ТС]
	А что проверить?Вот время моей программы1,218 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	02.05.2022, 09:18
	а у тебя счетчик вниз идет, тогда проверяй от корня из n 0

@thyrex 14433 / 7475 / 1579 Регистрация: 06.09.2009 Сообщений: 27,112
	02.05.2022, 09:23
	eaa, в сообщении №2 автору и был дан вариант проверки вниз от корня из n 0

Разбиение на квадраты

Решение