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

@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()

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .

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

	Разбиение на квадраты 01.05.2022, 10:37. Показов 2279. Ответов 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 14450 / 7489 / 1582 Регистрация: 06.09.2009 Сообщений: 27,133
	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 14450 / 7489 / 1582 Регистрация: 06.09.2009 Сообщений: 27,133
	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 14450 / 7489 / 1582 Регистрация: 06.09.2009 Сообщений: 27,133
	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 14450 / 7489 / 1582 Регистрация: 06.09.2009 Сообщений: 27,133
	02.05.2022, 09:23
	eaa, в сообщении №2 автору и был дан вариант проверки вниз от корня из n 0

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

Решение